Changeset 152

Timestamp:

04/22/08 17:28:26 (16 years ago)

Author:

gkronber

Message:

bug-fixes and code cleanup in struct-id operators (#112)

Location:

branches/FunctionsAndStructIdRefactoring/HeuristicLab.StructureIdentification

Files:

• GPOperatorGroup.cs (modified) (3 diffs)
• Manipulation/ChangeNodeTypeManipulation.cs (modified) (5 diffs)
• Manipulation/CutOutNodeManipulation.cs (modified) (1 diff)
• Manipulation/DeleteSubTreeManipulation.cs (modified) (1 diff)
• Manipulation/SubstituteSubTreeManipulation.cs (modified) (1 diff)
• Recombination/SinglePointCrossOver.cs (modified) (7 diffs)
• TreeGardener.cs (modified) (5 diffs)

branches/FunctionsAndStructIdRefactoring/HeuristicLab.StructureIdentification/GPOperatorGroup.cs

@@ -32 +32 @@
 namespace HeuristicLab.StructureIdentification {
   public class GPOperatorGroup : OperatorGroup {
-
     public GPOperatorGroup()
       : base() {
@@ -118 +117 @@
       int maxArity;
       GetMinMaxArity(op, out minArity, out maxArity);
-      ItemList slotsList = (ItemList)op.GetVariable(GPOperatorLibrary.ALLOWED_SUBOPERATORS).Value;
+      var slotsList = (ItemList)op.GetVariable(GPOperatorLibrary.ALLOWED_SUBOPERATORS).Value;
       slotsList.Clear();
       for(int i = 0; i < maxArity; i++) {
@@ -276 +275 @@
     }
 
-
     public override void AddSubGroup(IOperatorGroup group) {
       throw new NotSupportedException();

branches/FunctionsAndStructIdRefactoring/HeuristicLab.StructureIdentification/Manipulation/ChangeNodeTypeManipulation.cs

@@ -81 +81 @@
           // updating the variable is not necessary because it stays the same
         }
+        if(!gardener.IsValidTree(root)) throw new InvalidProgramException();
 
         // size and height stays the same when changing a terminal so no need to update the variables
@@ -105 +106 @@
         treeHeight.Data = gardener.GetTreeHeight(root);
 
+        // check if whole tree is ok
         // check if the size of the new tree is still in the allowed bounds
-        if (treeHeight.Data > maxTreeHeight ||
+        if (!gardener.IsValidTree(root) ||
+          treeHeight.Data > maxTreeHeight ||
           treeSize.Data > maxTreeSize) {
           throw new InvalidProgramException();
         }
 
-        // check if whole tree is ok
-        if (!gardener.IsValidTree(root)) {
-          throw new InvalidProgramException();
-        }
-
         // return a composite operation that initializes all created sub-trees
         return gardener.CreateInitializationOperation(uninitializedBranches, scope);
       }
     }
-
 
     private IFunctionTree ChangeTerminalType(IFunctionTree parent, IFunctionTree child, int childIndex, TreeGardener gardener, MersenneTwister random) {
@@ -127 +124 @@
         allowedChildren = gardener.Terminals;
       } else {
-        SubOperatorsConstraintAnalyser analyser = new SubOperatorsConstraintAnalyser();
-        analyser.AllPossibleOperators = gardener.Terminals.Cast<IOperator>().ToArray();
-        allowedChildren = analyser.GetAllowedOperators(parent.Function, childIndex).Cast<IFunction>().ToList();
+        allowedChildren = new List<IFunction>();
+        var allAllowedChildren = gardener.GetAllowedSubFunctions(parent.Function, childIndex);
+        foreach(IFunction c in allAllowedChildren) {
+          if(gardener.IsTerminal(c)) allowedChildren.Add(c);
+        }
       }
 
@@ -144 +143 @@
       // let's choose the function we want to use instead of the old child. For this we have to determine the
       // pool of allowed functions based on constraints of the parent if there is one.
-      IList<IFunction> allowedFunctions;
-      SubOperatorsConstraintAnalyser analyser = new SubOperatorsConstraintAnalyser();
-      analyser.AllPossibleOperators = gardener.AllFunctions.Cast<IOperator>().ToArray();
-      if (parent == null) {
-        allowedFunctions = gardener.AllFunctions;
-      } else {
-        allowedFunctions = analyser.GetAllowedOperators(parent.Function, childIndex).Cast<IFunction>().ToList();
-      }
+      IList<IFunction> allowedFunctions = gardener.GetAllowedSubFunctions(parent!=null?parent.Function:null, childIndex);
 
       // try to make a tree with the same arity as the old child.
@@ -190 +182 @@
         // then use a random existing sub-tree. When there are no existing sub-trees
         // that fit in the given slot then create a new random tree and use it for the slot
-        IList<IFunction> allowedSubFunctions = analyser.GetAllowedOperators(newTree.Function, i).Cast<IFunction>().ToList();
+        ICollection<IFunction> allowedSubFunctions = gardener.GetAllowedSubFunctions(newTree.Function, i);
         var matchingSubTrees = availableSubTrees.Where(subTree => allowedSubFunctions.Contains(subTree.Function));
 

branches/FunctionsAndStructIdRefactoring/HeuristicLab.StructureIdentification/Manipulation/CutOutNodeManipulation.cs

@@ -108 +108 @@
 
       // match the sub-trees of the child with the allowed sub-trees of the parent
-      IList<IFunction> allowedFunctions = gardener.GetAllowedSubFunctions(parent.Function, childIndex);
+      ICollection<IFunction> allowedFunctions = gardener.GetAllowedSubFunctions(parent.Function, childIndex);
       IFunctionTree[] possibleChilds = child.SubTrees.Where(t => allowedFunctions.Contains(t.Function)).ToArray();
 

branches/FunctionsAndStructIdRefactoring/HeuristicLab.StructureIdentification/Manipulation/DeleteSubTreeManipulation.cs

@@ -100 +100 @@
         parent.RemoveSubTree(childIndex);
 
-        IList<IFunction> allowedFunctions = gardener.GetAllowedSubFunctions(parent.Function, childIndex);
+        ICollection<IFunction> allowedFunctions = gardener.GetAllowedSubFunctions(parent.Function, childIndex);
         IFunctionTree newFunctionTree = gardener.CreateRandomTree(allowedFunctions, 1, 1, true);
 

branches/FunctionsAndStructIdRefactoring/HeuristicLab.StructureIdentification/Manipulation/SubstituteSubTreeManipulation.cs

@@ -88 +88 @@
         int childIndex = random.Next(parent.SubTrees.Count);
         // get the list of allowed functions for the new sub-tree
-        IList<IFunction> allowedFunctions = gardener.GetAllowedSubFunctions(parent.Function, childIndex);
+        ICollection<IFunction> allowedFunctions = gardener.GetAllowedSubFunctions(parent.Function, childIndex);
         if(allowedFunctions.Count == 0) {
           // don't change anything

branches/FunctionsAndStructIdRefactoring/HeuristicLab.StructureIdentification/Recombination/SinglePointCrossOver.cs

@@ -78 +78 @@
     }
 
-
     private IOperation Cross(TreeGardener gardener, int maxTreeSize, int maxTreeHeight,
       IScope scope, MersenneTwister random, IScope parent1, IScope parent2, IScope child) {
@@ -85 +84 @@
         random, maxTreeSize, maxTreeHeight, out newBranches);
 
-      if(!gardener.IsValidTree(newTree)) {
-        throw new InvalidProgramException();
-      }
 
       int newTreeSize = gardener.GetTreeSize(newTree);
       int newTreeHeight = gardener.GetTreeHeight(newTree);
-      child.AddVariable(new HeuristicLab.Core.Variable("FunctionTree", newTree));
-      child.AddVariable(new HeuristicLab.Core.Variable("TreeSize", new IntData(newTreeSize)));
-      child.AddVariable(new HeuristicLab.Core.Variable("TreeHeight", new IntData(newTreeHeight)));
-
-      // check if the size of the new tree is still in the allowed bounds
-      if (newTreeHeight > maxTreeHeight ||
+      child.AddVariable(new HeuristicLab.Core.Variable(scope.TranslateName("FunctionTree"), newTree));
+      child.AddVariable(new HeuristicLab.Core.Variable(scope.TranslateName("TreeSize"), new IntData(newTreeSize)));
+      child.AddVariable(new HeuristicLab.Core.Variable(scope.TranslateName("TreeHeight"), new IntData(newTreeHeight)));
+
+      // check if the new tree is valid and if the size of is still in the allowed bounds
+      if(!gardener.IsValidTree(newTree) ||
+        newTreeHeight > maxTreeHeight ||
         newTreeSize > maxTreeSize) {
         throw new InvalidProgramException();
@@ -139 +136 @@
 
         List<int> possibleChildIndices = new List<int>();
-        TreeGardener.FunctionEqualityComparer comparer = new TreeGardener.FunctionEqualityComparer();
 
         // Now tree0 is supposed to take tree1 as one if its children. If this is not possible,
         // then go down in either of the two trees as far as possible. If even then it is not possible
         // to merge the trees then throw an exception
-        // find the list of allowed indices (regarding allowed sub-operators, maxTreeSize and maxTreeHeight)
+        // find the list of allowed indices (regarding allowed sub-trees, maxTreeSize and maxTreeHeight)
         for(int i = 0; i < tree0.SubTrees.Count; i++) {
           int subTreeSize = gardener.GetTreeSize(tree0.SubTrees[i]);
 
           // the index is ok when the function is allowed as sub-tree and we don't violate the maxSize and maxHeight constraints
-          if(GetAllowedOperators(tree0.Function, i).Contains(tree1.Function, comparer) &&
+          if(gardener.GetAllowedSubFunctions(tree0.Function, i).Contains(tree1.Function) &&
             rootSize - subTreeSize + tree1Size < maxTreeSize &&
             tree0Level + tree1Height < maxTreeHeight) {
@@ -157 +153 @@
 
         while(possibleChildIndices.Count == 0) {
-          // ok we couln't find a possible configuration given the current tree0 and tree1
+          // we couln't find a possible configuration given the current tree0 and tree1
           // possible reasons for this are: 
           //  - tree1 is not allowed as sub-tree of tree0
@@ -187 +183 @@
             // when the function is allowed as sub-tree and we don't violate the maxSize and maxHeight constraints
             // the index is ok
-            if(GetAllowedOperators(tree0.Function, i).Contains(tree1.Function, comparer) &&
+            if(gardener.GetAllowedSubFunctions(tree0.Function, i).Contains(tree1.Function) &&
               rootSize - subTreeSize + tree1Size < maxTreeSize &&
               tree0Level + tree1Height < maxTreeHeight) {
@@ -211 +207 @@
     }
 
-    private ICollection<IFunction> GetAllowedOperators(IFunction f, int i) {
-      ItemList slotList = (ItemList)f.GetVariable(GPOperatorLibrary.ALLOWED_SUBOPERATORS).Value;
-      return ((ItemList)slotList[i]).Cast<IFunction>().ToArray();
-    }
-
+
+    // take f and g and create a tree that has f and g as sub-trees 
+    // example
+    //       O
+    //      /|\
+    //     g 2 f 
+    //
     private IFunctionTree CombineTerminals(TreeGardener gardener, IFunctionTree f, IFunctionTree g, MersenneTwister random, int maxTreeHeight, out List<IFunctionTree> newBranches) {
       newBranches = new List<IFunctionTree>();
+      // determine the set of possible parent functions
       ICollection<IFunction> possibleParents = gardener.GetPossibleParents(new List<IFunction>() { f.Function, g.Function });
       if(possibleParents.Count == 0) throw new InvalidProgramException();
-
+      // and select a random one
       IFunctionTree parent = new FunctionTree(possibleParents.ElementAt(random.Next(possibleParents.Count())));
 
@@ -226 +225 @@
       int maxArity;
       gardener.GetMinMaxArity(parent.Function, out minArity, out maxArity);
-
       int nSlots = Math.Max(2, minArity);
-
-      HashSet<IFunction>[] slotSets = new HashSet<IFunction>[nSlots];
-
-      SubOperatorsConstraintAnalyser analyser = new SubOperatorsConstraintAnalyser();
-      analyser.AllPossibleOperators = new List<IOperator>() { g.Function, f.Function };
+      // determine which slot can take which sub-trees
+      List<IFunctionTree>[] slots = new List<IFunctionTree>[nSlots];
       for(int slot = 0; slot < nSlots; slot++) {
-        HashSet<IFunction> slotSet = new HashSet<IFunction>(analyser.GetAllowedOperators(parent.Function, slot).Cast<IFunction>());
-        slotSets[slot] = slotSet;
-      }
-
-      int[] slotSequence = Enumerable.Range(0, slotSets.Count()).OrderBy(slot => slotSets[slot].Count()).ToArray();
-
+        ICollection<IFunction> allowedSubFunctions = gardener.GetAllowedSubFunctions(parent.Function, slot);
+        List<IFunctionTree> allowedTrees = new List<IFunctionTree>();
+        if(allowedSubFunctions.Contains(f.Function)) allowedTrees.Add(f);
+        if(allowedSubFunctions.Contains(g.Function)) allowedTrees.Add(g);
+        slots[slot] = allowedTrees;
+      }
+      // fill the slots in the order of degrees of freedom
+      int[] slotSequence = Enumerable.Range(0, slots.Count()).OrderBy(slot => slots[slot].Count()).ToArray();
+
+      // tmp arry to store the tree for each sub-tree slot of the parent
       IFunctionTree[] selectedFunctionTrees = new IFunctionTree[nSlots];
+
+      // fill the sub-tree slots of the parent starting with the slots that can take potentially both functions (f and g)
       for(int i = 0; i < slotSequence.Length; i++) {
         int slot = slotSequence[i];
-        HashSet<IFunction> slotSet = slotSets[slot];
-        if(slotSet.Count() == 0) {
-          var allowedFunctions = GetAllowedOperators(parent.Function, slot);
+        List<IFunctionTree> allowedTrees = slots[slot];
+        // when neither f nor g fit into the slot => create a new random tree
+        if(allowedTrees.Count() == 0) {
+          var allowedFunctions = gardener.GetAllowedSubFunctions(parent.Function, slot);
           selectedFunctionTrees[slot] = gardener.CreateRandomTree(allowedFunctions, 1, 1, true);
           newBranches.AddRange(gardener.GetAllSubTrees(selectedFunctionTrees[slot]));
         } else {
-          IFunction selectedFunction = slotSet.ElementAt(random.Next(slotSet.Count()));
-          selectedFunctionTrees[slot] = new FunctionTree(selectedFunction);
+          // select randomly which tree to insert into this slot
+          IFunctionTree selectedTree = allowedTrees[random.Next(allowedTrees.Count())];
+          selectedFunctionTrees[slot] = selectedTree;
+          // remove the tree that we used in this slot from following function-sets
           for(int j = i + 1; j < slotSequence.Length; j++) {
             int otherSlot = slotSequence[j];
-            slotSets[otherSlot].Remove(selectedFunction);
-          }
-        }
-      }
-
+            slots[otherSlot].Remove(selectedTree);
+          }
+        }
+      }
+      // actually append the sub-trees to the parent tree
       for(int i = 0; i < selectedFunctionTrees.Length; i++) {
         parent.InsertSubTree(i, selectedFunctionTrees[i]);

branches/FunctionsAndStructIdRefactoring/HeuristicLab.StructureIdentification/TreeGardener.cs

@@ -32 +32 @@
 using HeuristicLab.Selection;
 using HeuristicLab.Functions;
+using System.Collections;
 
 namespace HeuristicLab.StructureIdentification {
   internal class TreeGardener {
     private IRandom random;
-    private IOperatorLibrary funLibrary;
+    private GPOperatorLibrary funLibrary;
     private List<IFunction> functions;
     private List<IFunction> terminals;
@@ -49 +50 @@
     }
 
-    internal TreeGardener(IRandom random, IOperatorLibrary funLibrary) {
+    internal TreeGardener(IRandom random, GPOperatorLibrary funLibrary) {
       this.random = random;
       this.funLibrary = funLibrary;
@@ -254 +255 @@
         return allFunctions;
       } else {
-
-        SubOperatorsConstraintAnalyser analyser = new SubOperatorsConstraintAnalyser();
-        analyser.AllPossibleOperators = allFunctions.Cast<IOperator>().ToArray<IOperator>();
-
-        return analyser.GetAllowedOperators(f, index).Cast<IFunction>().ToList<IFunction>();
+        ItemList slotList = (ItemList)f.GetVariable(GPOperatorLibrary.ALLOWED_SUBOPERATORS).Value;
+        List<IFunction> result = new List<IFunction>();
+        foreach(IFunction function in (ItemList)slotList[index]) {
+          result.Add(function);
+        }
+        return result;
       }
     }
@@ -284 +286 @@
       List<IFunction> parents = new List<IFunction>();
       foreach (IFunction function in functions) {
-        IList<IFunction> allowedSubFunctions = GetAllowedSubFunctions(function, childIndex);
-        if (allowedSubFunctions.Contains(child, new FunctionEqualityComparer())) {
+        ICollection<IFunction> allowedSubFunctions = GetAllowedSubFunctions(function, childIndex);
+        if (allowedSubFunctions.Contains(child)) {
           parents.Add(function);
         }
@@ -377 +379 @@
     #endregion
 
-    internal class FunctionEqualityComparer : IEqualityComparer<IFunction> {
-      #region IEqualityComparer<IFunction> Members
-      public bool Equals(IFunction x, IFunction y) {
-        return  x==y || 
-          ((StringData)x.GetVariable(GPOperatorLibrary.TYPE_ID).Value).Data ==
-          ((StringData)y.GetVariable(GPOperatorLibrary.TYPE_ID).Value).Data;
-      }
-
-      public int GetHashCode(IFunction obj) {
-        return ((StringData)obj.GetVariable(GPOperatorLibrary.TYPE_ID).Value).Data.GetHashCode();
-      }
-      #endregion
-    }
-
     internal ICollection<IFunction> GetPossibleParents(List<IFunction> list) {
       List<IFunction> result = new List<IFunction>();