Changeset 155 for trunk/sources/HeuristicLab.StructureIdentification/Recombination

Timestamp:

04/22/08 18:05:14 (17 years ago)

Author:

gkronber

Message:

merged FunctionsAndStructIdRefactoring-branch (r142, r143, r144, r145, r146, r147, r148, r149, r152, r153) back into the trunk (ticket #112)

File:

• trunk/sources/HeuristicLab.StructureIdentification/Recombination/SinglePointCrossOver.cs (modified) (10 diffs)

trunk/sources/HeuristicLab.StructureIdentification/Recombination/SinglePointCrossOver.cs

@@ -29 +29 @@
 using HeuristicLab.Data;
 using HeuristicLab.Constraints;
+using HeuristicLab.Functions;
 
 namespace HeuristicLab.StructureIdentification {
@@ -44 +45 @@
       AddVariableInfo(new VariableInfo("MaxTreeHeight", "The maximal allowed height of the tree", typeof(IntData), VariableKind.In));
       AddVariableInfo(new VariableInfo("MaxTreeSize", "The maximal allowed size (number of nodes) of the tree", typeof(IntData), VariableKind.In));
-      AddVariableInfo(new VariableInfo("OperatorTree", "The tree to mutate", typeof(IOperator), VariableKind.In));
-      AddVariableInfo(new VariableInfo("TreeSize", "The size (number of nodes) of the tree", typeof(IntData), VariableKind.In));
-      AddVariableInfo(new VariableInfo("TreeHeight", "The height of the tree", typeof(IntData), VariableKind.In));
+      AddVariableInfo(new VariableInfo("FunctionTree", "The tree to mutate", typeof(IFunctionTree), VariableKind.In | VariableKind.New));
+      AddVariableInfo(new VariableInfo("TreeSize", "The size (number of nodes) of the tree", typeof(IntData), VariableKind.New));
+      AddVariableInfo(new VariableInfo("TreeHeight", "The height of the tree", typeof(IntData), VariableKind.New));
     }
 
@@ -77 +78 @@
     }
 
-
     private IOperation Cross(TreeGardener gardener, int maxTreeSize, int maxTreeHeight,
       IScope scope, MersenneTwister random, IScope parent1, IScope parent2, IScope child) {
-      List<IOperator> newOperators;
-      IOperator newTree = Cross(gardener, parent1, parent2,
-        random, maxTreeSize, maxTreeHeight, out newOperators);
-
-      if(!gardener.IsValidTree(newTree)) {
-        throw new InvalidProgramException();
-      }
+      List<IFunctionTree> newBranches;
+      IFunctionTree newTree = Cross(gardener, parent1, parent2,
+        random, maxTreeSize, maxTreeHeight, out newBranches);
+
 
       int newTreeSize = gardener.GetTreeSize(newTree);
       int newTreeHeight = gardener.GetTreeHeight(newTree);
-      child.AddVariable(new Variable("OperatorTree", newTree));
-      child.AddVariable(new Variable("TreeSize", new IntData(newTreeSize)));
-      child.AddVariable(new 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();
       }
-
-
-      return gardener.CreateInitializationOperation(newOperators, child);
-    }
-
-
-    private IOperator Cross(TreeGardener gardener, IScope f, IScope g, MersenneTwister random, int maxTreeSize, int maxTreeHeight, out List<IOperator> newOperators) {
-      IOperator tree0 = f.GetVariableValue<IOperator>("OperatorTree", false);
+      return gardener.CreateInitializationOperation(newBranches, child);
+    }
+
+
+    private IFunctionTree Cross(TreeGardener gardener, IScope f, IScope g, MersenneTwister random, int maxTreeSize, int maxTreeHeight, out List<IFunctionTree> newBranches) {
+      IFunctionTree tree0 = f.GetVariableValue<IFunctionTree>("FunctionTree", false);
       int tree0Height = f.GetVariableValue<IntData>("TreeHeight", false).Data;
       int tree0Size = f.GetVariableValue<IntData>("TreeSize", false).Data;
 
-      IOperator tree1 = g.GetVariableValue<IOperator>("OperatorTree", false);
+      IFunctionTree tree1 = g.GetVariableValue<IFunctionTree>("FunctionTree", false);
       int tree1Height = g.GetVariableValue<IntData>("TreeHeight", false).Data;
       int tree1Size = g.GetVariableValue<IntData>("TreeSize", false).Data;
 
       if(tree0Size == 1 && tree1Size == 1) {
-        return CombineTerminals(gardener, tree0, tree1, random, maxTreeHeight, out newOperators);
+        return CombineTerminals(gardener, tree0, tree1, random, maxTreeHeight, out newBranches);
       } else {
         // we are going to insert tree1 into tree0 at a random place so we have to make sure that tree0 is not a terminal
         // in case both trees are higher than 1 we swap the trees with probability 50%
         if(tree0Height == 1 || (tree1Height > 1 && random.Next(2) == 0)) {
-          IOperator tmp = tree0; tree0 = tree1; tree1 = tmp;
+          IFunctionTree tmp = tree0; tree0 = tree1; tree1 = tmp;
           int tmpHeight = tree0Height; tree0Height = tree1Height; tree1Height = tmpHeight;
           int tmpSize = tree0Size; tree0Size = tree1Size; tree1Size = tmpSize;
@@ -126 +122 @@
 
         // save the root because later on we change tree0 and tree1 while searching a valid tree configuration
-        IOperator root = tree0;
+        IFunctionTree root = tree0;
         int rootSize = tree0Size;
 
@@ -132 +128 @@
         int tree0Level = random.Next(tree0Height - 1); // since we checked before that the height of tree0 is > 1 this is OK
         int tree1Level = random.Next(tree1Height);
-        tree0 = gardener.GetRandomNode(tree0, tree0Level);
-        tree1 = gardener.GetRandomNode(tree1, tree1Level);
+        tree0 = gardener.GetRandomBranch(tree0, tree0Level);
+        tree1 = gardener.GetRandomBranch(tree1, tree1Level);
 
         // recalculate the size and height of tree1 (the one that we want to insert) because we need to check constraints later on
@@ -140 +136 @@
 
         List<int> possibleChildIndices = new List<int>();
-        TreeGardener.OperatorEqualityComparer comparer = new TreeGardener.OperatorEqualityComparer();
 
         // 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)
-        for(int i = 0; i < tree0.SubOperators.Count; i++) {
-          int subOperatorSize = gardener.GetTreeSize(tree0.SubOperators[i]);
-
-          // the index is ok when the operator is allowed as sub-operator and we don't violate the maxSize and maxHeight constraints
-          if(GetAllowedOperators(tree0, i).Contains(tree1, comparer) &&
-            rootSize - subOperatorSize + tree1Size < maxTreeSize &&
+        // 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(gardener.GetAllowedSubFunctions(tree0.Function, i).Contains(tree1.Function) &&
+            rootSize - subTreeSize + tree1Size < maxTreeSize &&
             tree0Level + tree1Height < maxTreeHeight) {
             possibleChildIndices.Add(i);
@@ -158 +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-operator of tree0
+          //  - tree1 is not allowed as sub-tree of tree0
           //  - appending tree1 as child of tree0 would create a tree that exceedes the maxTreeHeight
           //  - replacing any child of tree0 with tree1 woulde create a tree that exceedes the maxTeeSize
@@ -166 +161 @@
           //  - go up in tree0 => the insert position allows larger trees
           //  - go down in tree1 => the tree that is inserted becomes smaller
-          //  - however we have to get lucky to solve the 'allowed sub-operators' problem
+          //  - however we have to get lucky to solve the 'allowed sub-trees' problem
           if(tree1Height == 1 || (tree0Level>0 && random.Next(2) == 0)) {
             // go up in tree0 
             tree0Level--;
-            tree0 = gardener.GetRandomNode(root, tree0Level);
-          } else if(tree1.SubOperators.Count > 0) {
+            tree0 = gardener.GetRandomBranch(root, tree0Level);
+          } else if(tree1.SubTrees.Count > 0) {
             // go down in node2:
-            tree1 = tree1.SubOperators[random.Next(tree1.SubOperators.Count)];
+            tree1 = tree1.SubTrees[random.Next(tree1.SubTrees.Count)];
             tree1Size = gardener.GetTreeSize(tree1);
             tree1Height = gardener.GetTreeHeight(tree1);
@@ -183 +178 @@
           // recalculate the list of possible indices 
           possibleChildIndices.Clear();
-          for(int i = 0; i < tree0.SubOperators.Count; i++) {
-            int subOperatorSize = gardener.GetTreeSize(tree0.SubOperators[i]);
-
-            // when the operator is allowed as sub-operator and we don't violate the maxSize and maxHeight constraints
+          for(int i = 0; i < tree0.SubTrees.Count; i++) {
+            int subTreeSize = gardener.GetTreeSize(tree0.SubTrees[i]);
+
+            // 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, i).Contains(tree1, comparer) &&
-              rootSize - subOperatorSize + tree1Size < maxTreeSize &&
+            if(gardener.GetAllowedSubFunctions(tree0.Function, i).Contains(tree1.Function) &&
+              rootSize - subTreeSize + tree1Size < maxTreeSize &&
               tree0Level + tree1Height < maxTreeHeight) {
               possibleChildIndices.Add(i);
@@ -203 +198 @@
         // replace the existing sub-tree at a random index in tree0 with tree1
         int selectedIndex = possibleChildIndices[random.Next(possibleChildIndices.Count)];
-        tree0.RemoveSubOperator(selectedIndex);
-        tree0.AddSubOperator(tree1, selectedIndex);
+        tree0.RemoveSubTree(selectedIndex);
+        tree0.InsertSubTree(selectedIndex, tree1);
 
         // no new operators where needed
-        newOperators = new List<IOperator>();
+        newBranches = new List<IFunctionTree>();
         return root;
       }
     }
 
-    private ICollection<IOperator> GetAllowedOperators(IOperator tree0, int i) {
-      ItemList slotList = (ItemList)tree0.GetVariable(GPOperatorLibrary.ALLOWED_SUBOPERATORS).Value;
-      return ((ItemList)slotList[i]).OfType<IOperator>().ToArray();
-    }
-
-    private IOperator CombineTerminals(TreeGardener gardener, IOperator f, IOperator g, MersenneTwister random, int maxTreeHeight, out List<IOperator> newOperators) {
-      newOperators = new List<IOperator>();
-      ICollection<IOperator> possibleParents = gardener.GetPossibleParents(new List<IOperator>() { f, g });
+
+    // 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();
-
-      IOperator parent = (IOperator)possibleParents.ElementAt(random.Next(possibleParents.Count())).Clone();
+      // and select a random one
+      IFunctionTree parent = new FunctionTree(possibleParents.ElementAt(random.Next(possibleParents.Count())));
 
       int minArity;
       int maxArity;
-      gardener.GetMinMaxArity(parent, out minArity, out maxArity);
-
+      gardener.GetMinMaxArity(parent.Function, out minArity, out maxArity);
       int nSlots = Math.Max(2, minArity);
-
-      HashSet<IOperator>[] slotSets = new HashSet<IOperator>[nSlots];
-
-      SubOperatorsConstraintAnalyser analyser = new SubOperatorsConstraintAnalyser();
-      analyser.AllPossibleOperators = new List<IOperator>() { g, f };
+      // determine which slot can take which sub-trees
+      List<IFunctionTree>[] slots = new List<IFunctionTree>[nSlots];
       for(int slot = 0; slot < nSlots; slot++) {
-        HashSet<IOperator> slotSet = new HashSet<IOperator>(analyser.GetAllowedOperators(parent, slot));
-        slotSets[slot] = slotSet;
-      }
-
-      int[] slotSequence = Enumerable.Range(0, slotSets.Count()).OrderBy(slot => slotSets[slot].Count()).ToArray();
-
-      IOperator[] selectedOperators = new IOperator[nSlots];
+        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<IOperator> slotSet = slotSets[slot];
-        if(slotSet.Count() == 0) {
-          var allowedOperators = GetAllowedOperators(parent, slot);
-          selectedOperators[slot] = gardener.CreateRandomTree(allowedOperators, 1, 1, true);
-          newOperators.AddRange(gardener.GetAllOperators(selectedOperators[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 {
-          IOperator selectedOperator = slotSet.ElementAt(random.Next(slotSet.Count()));
-          selectedOperators[slot] = selectedOperator;
+          // 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(selectedOperator);
-          }
-        }
-      }
-
-      for(int i = 0; i < selectedOperators.Length; i++) {
-        parent.AddSubOperator(selectedOperators[i], i);
+            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]);
       }