Free cookie consent management tool by TermsFeed Policy Generator

Changeset 4106


Ignore:
Timestamp:
07/26/10 16:18:45 (13 years ago)
Author:
gkronber
Message:

Fixed bugs in SubtreeCrossover, ArgumentCreater and ArgumentDuplicater and updated unit tests for symbolic expression tree operators. #1103

Location:
trunk/sources
Files:
10 edited

Legend:

Unmodified
Added
Removed
  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/ArchitectureManipulators/ArgumentCreater.cs

    r4068 r4106  
    8383      selectedCutPoint.Parent.RemoveSubTree(selectedCutPoint.ReplacedChildIndex);
    8484      selectedCutPoint.Parent.InsertSubTree(selectedCutPoint.ReplacedChildIndex, newArgNode);
     85
    8586      // find all invocations of the selected ADF and attach a cloned version of the replaced branch (with all argument-nodes expanded)
    8687      var invocationNodes = from node in symbolicExpressionTree.IterateNodesPrefix().OfType<InvokeFunctionTreeNode>()
    8788                            where node.Symbol.FunctionName == selectedDefunBranch.FunctionName
     89                            where node.SubTrees.Count == selectedDefunBranch.NumberOfArguments
    8890                            select node;
    89       foreach (var invocationNode in invocationNodes) {
    90         // append a new argument branch after expanding all argument nodes
    91         var clonedBranch = (SymbolicExpressionTreeNode)replacedBranch.Clone();
    92         clonedBranch = ReplaceArgumentsInBranch(clonedBranch, invocationNode.SubTrees);
    93         invocationNode.InsertSubTree(newArgumentIndex, clonedBranch);
     91      // do this repeatedly until no matching invocations are found     
     92      while (invocationNodes.Count() > 0) {
     93        List<SymbolicExpressionTreeNode> newlyAddedBranches = new List<SymbolicExpressionTreeNode>();
     94        foreach (var invocationNode in invocationNodes) {
     95          // append a new argument branch after expanding all argument nodes
     96          var clonedBranch = (SymbolicExpressionTreeNode)replacedBranch.Clone();
     97          clonedBranch = ReplaceArgumentsInBranch(clonedBranch, invocationNode.SubTrees);
     98          invocationNode.InsertSubTree(newArgumentIndex, clonedBranch);
     99          newlyAddedBranches.Add(clonedBranch);
     100        }
     101        invocationNodes = from newlyAddedBranch in newlyAddedBranches
     102                          from node in newlyAddedBranch.IterateNodesPrefix().OfType<InvokeFunctionTreeNode>()
     103                          where node.Symbol.FunctionName == selectedDefunBranch.FunctionName
     104                          where node.SubTrees.Count == selectedDefunBranch.NumberOfArguments
     105                          select node;
    94106      }
    95107      // increase expected number of arguments of function defining branch
  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/ArchitectureManipulators/ArgumentDuplicater.cs

    r4068 r4106  
    2525using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Symbols;
    2626using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     27using System.Collections.Generic;
    2728
    2829namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ArchitectureManipulators {
     
    8081      var invocationNodes = from node in symbolicExpressionTree.IterateNodesPrefix().OfType<InvokeFunctionTreeNode>()
    8182                            where node.Symbol.FunctionName == selectedDefunBranch.FunctionName
     83                            where node.SubTrees.Count == selectedDefunBranch.NumberOfArguments
    8284                            select node;
    83       foreach (var invokeNode in invocationNodes) {
    84         var argumentBranch = invokeNode.SubTrees[selectedArgumentSymbol.ArgumentIndex];
    85         var clonedArgumentBranch = (SymbolicExpressionTreeNode)argumentBranch.Clone();
    86         invokeNode.InsertSubTree(newArgumentIndex, clonedArgumentBranch);
     85      // do this repeatedly until no matching invocations are found     
     86      while (invocationNodes.Count() > 0) {
     87        List<SymbolicExpressionTreeNode> newlyAddedBranches = new List<SymbolicExpressionTreeNode>();
     88        foreach (var invokeNode in invocationNodes) {
     89          var argumentBranch = invokeNode.SubTrees[selectedArgumentSymbol.ArgumentIndex];
     90          var clonedArgumentBranch = (SymbolicExpressionTreeNode)argumentBranch.Clone();
     91          invokeNode.InsertSubTree(newArgumentIndex, clonedArgumentBranch);
     92          newlyAddedBranches.Add(clonedArgumentBranch);
     93        }
     94        invocationNodes = from newlyAddedBranch in newlyAddedBranches
     95                          from node in newlyAddedBranch.IterateNodesPrefix().OfType<InvokeFunctionTreeNode>()
     96                          where node.Symbol.FunctionName == selectedDefunBranch.FunctionName
     97                          where node.SubTrees.Count == selectedDefunBranch.NumberOfArguments
     98                          select node;
    8799      }
    88100      // register the new argument symbol and increase the number of arguments of the ADF
  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Crossovers/SubtreeCrossover.cs

    r4068 r4106  
    9090    private static bool IsMatchingPointType(SymbolicExpressionTreeNode parent, int replacedSubtreeIndex, SymbolicExpressionTreeNode branch) {
    9191      // check syntax constraints of direct parent - child relation
    92       if (!parent.Grammar.IsAllowedChild(parent.Symbol, branch.Symbol, replacedSubtreeIndex)) return false;
     92      if (!parent.Grammar.ContainsSymbol(branch.Symbol) ||
     93          !parent.Grammar.IsAllowedChild(parent.Symbol, branch.Symbol, replacedSubtreeIndex)) return false;
    9394
    9495      bool result = true;
     
    9798        result =
    9899          result &&
     100          parent.Grammar.ContainsSymbol(n.Symbol) &&
    99101          n.SubTrees.Count >= parent.Grammar.GetMinSubtreeCount(n.Symbol) &&
    100           n.SubTrees.Count <= parent.Grammar.GetMaxSubtreeCount(n.Symbol) &&
    101           parent.Grammar.ContainsSymbol(n.Symbol);
     102          n.SubTrees.Count <= parent.Grammar.GetMaxSubtreeCount(n.Symbol);
    102103      });
    103104      return result;
  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/SymbolicExpressionTreeNode.cs

    r4068 r4106  
    5151    }
    5252
    53     public SymbolicExpressionTreeNode() {
     53    internal SymbolicExpressionTreeNode() {
    5454      // don't allocate subtrees list here!
    5555      // because we don't want to allocate it in terminal nodes
     
    8585    }
    8686
    87     internal virtual ISymbolicExpressionGrammar Grammar {
     87    public virtual ISymbolicExpressionGrammar Grammar {
    8888      get { return parent.Grammar; }
    8989      set { throw new NotSupportedException("Grammar can be set only for SymbolicExpressionTreeTopLevelNodes."); }
     
    9494      else {
    9595        size = 1;
    96         for (int i = 0; i < SubTrees.Count; i++) size += (short)SubTrees[i].GetSize();
     96        if (SubTrees != null) {
     97          for (int i = 0; i < SubTrees.Count; i++) size += (short)SubTrees[i].GetSize();
     98        }
    9799        return size;
    98100      }
     
    102104      if (height > 0) return height;
    103105      else {
    104         for (int i = 0; i < SubTrees.Count; i++) height = Math.Max(height, (short)SubTrees[i].GetHeight());
     106        if (SubTrees != null) {
     107          for (int i = 0; i < SubTrees.Count; i++) height = Math.Max(height, (short)SubTrees[i].GetHeight());
     108        }
    105109        height++;
    106110        return height;
     
    112116
    113117    public virtual void AddSubTree(SymbolicExpressionTreeNode tree) {
    114       subTrees.Add(tree);
     118      SubTrees.Add(tree);
    115119      tree.Parent = this;
    116120      ResetCachedValues();
     
    118122
    119123    public virtual void InsertSubTree(int index, SymbolicExpressionTreeNode tree) {
    120       subTrees.Insert(index, tree);
     124      SubTrees.Insert(index, tree);
    121125      tree.Parent = this;
    122126      ResetCachedValues();
     
    124128
    125129    public virtual void RemoveSubTree(int index) {
    126       subTrees[index].Parent = null;
    127       subTrees.RemoveAt(index);
     130      SubTrees[index].Parent = null;
     131      SubTrees.RemoveAt(index);
    128132      ResetCachedValues();
    129133    }
     
    137141    public void ForEachNodePrefix(Action<SymbolicExpressionTreeNode> a) {
    138142      a(this);
    139       for (int i = 0; i < SubTrees.Count; i++) {
    140         SubTrees[i].ForEachNodePrefix(a);
     143      if (SubTrees != null) {
     144        for (int i = 0; i < SubTrees.Count; i++) {
     145          SubTrees[i].ForEachNodePrefix(a);
     146        }
    141147      }
    142148    }
     
    149155
    150156    public void ForEachNodePostfix(Action<SymbolicExpressionTreeNode> a) {
    151       for (int i = 0; i < SubTrees.Count; i++) {
    152         SubTrees[i].ForEachNodePrefix(a);
     157      if (SubTrees != null) {
     158        for (int i = 0; i < SubTrees.Count; i++) {
     159          SubTrees[i].ForEachNodePostfix(a);
     160        }
    153161      }
    154162      a(this);
  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/SymbolicExpressionTreeTopLevelNode.cs

    r4068 r4106  
    3737    [Storable]
    3838    private ISymbolicExpressionGrammar grammar;
    39     internal override ISymbolicExpressionGrammar Grammar {
     39    public override ISymbolicExpressionGrammar Grammar {
    4040      get { return grammar; }
    4141      set { grammar = value; }
  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Symbols/InvokeFunction.cs

    r4068 r4106  
    3232  public sealed class InvokeFunction : ReadOnlySymbol {
    3333    public const string InvokeFunctionName = "InvokeFunction";
    34     public const string InvokeFunctionDescription = "Symbol that the invokation of another function.";
     34    public const string InvokeFunctionDescription = "Symbol that the invocation of another function.";
    3535    public override bool CanChangeName {
    3636      get {
  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Tests/Grammars.cs

    r4068 r4106  
    2626namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding_3._3.Tests {
    2727  public static class Grammars {
    28     private class Addition : Symbol { }
    29     private class Subtraction : Symbol { }
    30     private class Multiplication : Symbol { }
    31     private class Division : Symbol { }
    32     private class Terminal : Symbol { }
     28    private class Addition : Symbol { public Addition() : base("Addition", "") { } }
     29    private class Subtraction : Symbol { public Subtraction() : base("Subtraction", "") { } }
     30    private class Multiplication : Symbol { public Multiplication() : base("Multiplication", "") { } }
     31    private class Division : Symbol { public Division() : base("Division", "") { } }
     32    private class Terminal : Symbol { public Terminal() : base("Terminal", "") { } }
    3333
    3434    private class SimpleArithmeticGrammar : DefaultSymbolicExpressionGrammar {
     
    8989      return g;
    9090    }
    91 
    92     public static void HasValidAdfGrammars(SymbolicExpressionTree tree) {
    93       //Assert.AreEqual(tree.Root.Grammar.Symbols.Count(), 8);
    94       //Assert.AreEqual(tree.Root.GetAllowedSymbols(0).Count(), 1); // only the start symbol is allowed
    95       //// we allow 3 ADF branches
    96       //Assert.AreEqual(tree.Root.GetAllowedSymbols(1).Count(), 1); // only the defun branch is allowed
    97       //Assert.AreEqual(tree.Root.GetAllowedSymbols(2).Count(), 1); // only the defun symbol is allowed
    98       //Assert.AreEqual(tree.Root.GetAllowedSymbols(3).Count(), 1); // only the defun symbol is allowed
    99       //foreach (var subtree in tree.Root.SubTrees) {
    100       //  // check consistency of each sub-tree grammar independently
    101       //  var allowedSymbols = subtree.GetAllowedSymbols(0);
    102       //  int numberOfAllowedSymbols = allowedSymbols.Count();
    103       //  foreach (var parent in allowedSymbols) {
    104       //    for (int argIndex = 0; argIndex < subtree.Grammar.GetMaxSubtreeCount(parent); argIndex++) {
    105       //      var allowedChildren = from child in subtree.Grammar.Symbols
    106       //                            where subtree.Grammar.IsAllowedChild(parent, child, argIndex)
    107       //                            select child;
    108       //      Assert.AreEqual(numberOfAllowedSymbols, allowedChildren.Count());
    109       //    }
    110       //  }
    111       //}
    112     }
    113 
    11491  }
    11592}
  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Tests/ProbabilisticTreeCreaterTest.cs

    r4068 r4106  
    7676      for (int i = 0; i < POPULATION_SIZE; i++) {
    7777        var tree = ProbabilisticTreeCreator.Create(random, grammar, MAX_TREE_SIZE, MAX_TREE_HEIGHT, 3, 3);
    78         Grammars.HasValidAdfGrammars(tree);
    7978        Util.IsValid(tree);
    8079        randomTrees.Add(tree);
  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Tests/Util.cs

    r4068 r4106  
    2626using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
    2727using Microsoft.VisualStudio.TestTools.UnitTesting;
     28using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Symbols;
    2829
    2930namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding_3._3.Tests {
     
    114115
    115116    public static void IsValid(SymbolicExpressionTree tree) {
    116       Grammars.HasValidAdfGrammars(tree);
     117      foreach (var defunTreeNode in tree.Root.SubTrees.OfType<DefunTreeNode>()) {
     118        int arity = defunTreeNode.NumberOfArguments;
     119        var invoke = new InvokeFunction(defunTreeNode.FunctionName);
     120        foreach (var otherRootNode in tree.Root.SubTrees) {
     121          if (otherRootNode.Grammar.ContainsSymbol(invoke)) {
     122            Assert.IsTrue(otherRootNode.Grammar.GetMinSubtreeCount(invoke) == arity);
     123            Assert.IsTrue(otherRootNode.Grammar.GetMaxSubtreeCount(invoke) == arity);
     124          }
     125        }
     126      }
    117127      //Assert.AreEqual(tree.Root.Symbol, tree.Root.Grammar.StartSymbol);
    118128      //foreach (var subtree in tree.Root.SubTrees)
     
    122132
    123133    public static void IsValid(SymbolicExpressionTreeNode treeNode) {
    124       //var matchingSymbol = (from symb in treeNode.Grammar.Symbols
    125       //                      where symb.Name == treeNode.Symbol.Name
    126       //                      select symb).SingleOrDefault();
    127       //Assert.IsTrue(treeNode.SubTrees.Count >= treeNode.Grammar.GetMinSubtreeCount(matchingSymbol));
    128       //Assert.IsTrue(treeNode.SubTrees.Count <= treeNode.Grammar.GetMaxSubtreeCount(matchingSymbol));
     134      var matchingSymbol = (from symb in treeNode.Grammar.Symbols
     135                            where symb.Name == treeNode.Symbol.Name
     136                            select symb).SingleOrDefault();
     137      Assert.IsTrue(treeNode.SubTrees.Count >= treeNode.Grammar.GetMinSubtreeCount(matchingSymbol));
     138      Assert.IsTrue(treeNode.SubTrees.Count <= treeNode.Grammar.GetMaxSubtreeCount(matchingSymbol));
    129139      for (int i = 0; i < treeNode.SubTrees.Count; i++) {
    130140        Assert.IsTrue(treeNode.GetAllowedSymbols(i).Select(x => x.Name).Contains(treeNode.SubTrees[i].Symbol.Name));
  • trunk/sources/HeuristicLab.Problems.ArtificialAnt/3.3/ArtificialAntProblem.cs

    r4098 r4106  
    194194
    195195    [StorableConstructor]
    196     private ArtificialAntProblem(bool deserializing) : base() { }
     196    private ArtificialAntProblem(bool deserializing) : base(deserializing) { }
    197197    public ArtificialAntProblem()
    198198      : base() {
Note: See TracChangeset for help on using the changeset viewer.