Changeset 5792


Ignore:
Timestamp:
03/22/11 15:07:20 (11 years ago)
Author:
mkommend
Message:

#1418: Corrected ADFs and adapted unit tests.

Location:
branches/DataAnalysis Refactoring
Files:
10 edited

Legend:

Unmodified
Added
Removed
  • branches/DataAnalysis Refactoring/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/ArchitectureManipulators/ArgumentCreater.cs

    r5733 r5792  
    124124      // the branch at the cut point is to be replaced by a new argument node
    125125      var cutPoints = (from node in defunBranch.IterateNodesPrefix()
    126                        where node.Subtrees.Count() > 0
     126                       where node.Subtrees.Count() > 0 &&
     127                             !node.IterateNodesPrefix().OfType<ArgumentTreeNode>().Any() &&
     128                             !node.IterateNodesPrefix().OfType<InvokeFunctionTreeNode>().Any()
    127129                       from subtree in node.Subtrees
    128130                       select new CutPoint(node, subtree)).ToList();
     
    169171      defunBranch.Grammar.SetSubtreeCount(newArgumentNode.Symbol, 0, 0);
    170172      // allow the argument as child of any other symbol
    171       foreach (var symb in defunBranch.Grammar.Symbols)
    172         for (int i = 0; i < defunBranch.Grammar.GetMaximumSubtreeCount(symb); i++) {
    173           defunBranch.Grammar.AddAllowedChildSymbol(symb, newArgumentNode.Symbol, i);
    174         }
     173      GrammarModifier.SetAllowedParentSymbols(defunBranch.Grammar, selectedCutPoint.Child.Symbol, newArgumentNode.Symbol);
     174
    175175      foreach (var subtree in tree.Root.Subtrees) {
    176176        // when the changed function is known in the branch then update the number of arguments
     
    178178        if (matchingSymbol != null) {
    179179          subtree.Grammar.SetSubtreeCount(matchingSymbol, defunBranch.NumberOfArguments, defunBranch.NumberOfArguments);
    180           foreach (var child in subtree.Grammar.GetAllowedChildSymbols(subtree.Symbol, 0)) {
    181             for (int i = 0; i < subtree.Grammar.GetMaximumSubtreeCount(matchingSymbol); i++) {
    182               subtree.Grammar.AddAllowedChildSymbol(matchingSymbol, child, i);
    183             }
     180          foreach (var symb in subtree.Grammar.Symbols) {
     181            if (symb is StartSymbol || symb is ProgramRootSymbol) continue;
     182            if (subtree.Grammar.IsAllowedChildSymbol(selectedCutPoint.Parent.Symbol, symb, selectedCutPoint.ChildIndex))
     183              subtree.Grammar.AddAllowedChildSymbol(matchingSymbol, symb, newArgumentNode.Symbol.ArgumentIndex);
    184184          }
    185185        }
  • branches/DataAnalysis Refactoring/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/ArchitectureManipulators/ArgumentDuplicater.cs

    r5733 r5792  
    108108      selectedDefunBranch.Grammar.AddSymbol(newArgSymbol);
    109109      selectedDefunBranch.Grammar.SetSubtreeCount(newArgSymbol, 0, 0);
    110       // allow the argument as child of any other symbol
    111       foreach (var symb in selectedDefunBranch.Grammar.Symbols)
    112         for (int i = 0; i < selectedDefunBranch.Grammar.GetMaximumSubtreeCount(symb); i++) {
    113           selectedDefunBranch.Grammar.AddAllowedChildSymbol(symb, newArgSymbol, i);
    114         }
     110      // allow the duplicated argument as child of all other arguments where the orginal argument was allowed
     111      GrammarModifier.SetAllowedParentSymbols(selectedDefunBranch.Grammar, selectedArgumentSymbol, newArgSymbol);
    115112      selectedDefunBranch.NumberOfArguments++;
    116113
     
    122119        if (matchingInvokeSymbol != null) {
    123120          subtree.Grammar.SetSubtreeCount(matchingInvokeSymbol, selectedDefunBranch.NumberOfArguments, selectedDefunBranch.NumberOfArguments);
    124           foreach (var child in subtree.Grammar.GetAllowedChildSymbols(subtree.Symbol, 0)) {
    125             for (int i = 0; i < subtree.Grammar.GetMaximumSubtreeCount(matchingInvokeSymbol); i++) {
    126               subtree.Grammar.AddAllowedChildSymbol(matchingInvokeSymbol, child, i);
    127             }
     121          foreach (var symb in subtree.Grammar.Symbols) {
     122            if (symb is StartSymbol || symb is ProgramRootSymbol) continue;
     123            if (subtree.Grammar.IsAllowedChildSymbol(matchingInvokeSymbol, symb, selectedArgumentSymbol.ArgumentIndex))
     124              subtree.Grammar.AddAllowedChildSymbol(matchingInvokeSymbol, symb, newArgumentIndex);
    128125          }
    129126        }
  • branches/DataAnalysis Refactoring/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/ArchitectureManipulators/GrammarModifier.cs

    r5686 r5792  
    2626  public static class GrammarModifier {
    2727    internal static void AddInvokeSymbol(ISymbolicExpressionTreeGrammar grammar, string functionName, int nArgs, CutPoint startCutPoint, IEnumerable<CutPoint> argumentCutPoints) {
     28      if (!grammar.ContainsSymbol(startCutPoint.Child.Symbol)) return;
     29
    2830      var invokeSym = new InvokeFunction(functionName);
    2931      grammar.AddSymbol(invokeSym);
     
    3133
    3234      //allow invoke symbol everywhere, where the child of the startCutPoint was allowed
    33       foreach (ISymbol parent in grammar.Symbols) {
    34         if (grammar.IsAllowedChildSymbol(parent, startCutPoint.Child.Symbol))
    35           grammar.AddAllowedChildSymbol(parent, invokeSym);
    36         else {
    37           for (int i = 0; i < grammar.GetMaximumSubtreeCount(parent); i++) {
    38             if (grammar.IsAllowedChildSymbol(parent, startCutPoint.Child.Symbol, i))
    39               grammar.AddAllowedChildSymbol(parent, invokeSym, i);
    40           }
    41         }
    42       }
     35      SetAllowedParentSymbols(grammar, startCutPoint.Child.Symbol, invokeSym);
    4336
    4437      if (nArgs > 0) {
    4538        //set allowed child symbols of invoke symbol
    4639        foreach (ISymbol child in grammar.Symbols) {
    47           if (argumentCutPoints.All(x => grammar.IsAllowedChildSymbol(x.Parent.Symbol, child)))
    48             grammar.AddAllowedChildSymbol(invokeSym, child);
    49           else {
    50             int i = 0;
    51             foreach (CutPoint argumentCutPoint in argumentCutPoints) {
    52               if (grammar.IsAllowedChildSymbol(argumentCutPoint.Parent.Symbol, child, argumentCutPoint.ChildIndex))
    53                 grammar.AddAllowedChildSymbol(invokeSym, child, i);
    54               i++;
    55             }
     40          int i = 0;
     41          foreach (CutPoint argumentCutPoint in argumentCutPoints) {
     42            if (grammar.IsAllowedChildSymbol(argumentCutPoint.Parent.Symbol, child, argumentCutPoint.ChildIndex))
     43              grammar.AddAllowedChildSymbol(invokeSym, child, i);
     44            i++;
    5645          }
    5746        }
    5847      }
    5948    }
     49
     50
    6051
    6152    internal static void AddArgumentSymbol(ISymbolicExpressionTreeGrammar originalGrammar, ISymbolicExpressionTreeGrammar grammar, IEnumerable<int> argumentIndexes, IEnumerable<CutPoint> argumentCutPoints) {
     
    6556        grammar.SetSubtreeCount(argSymbol, 0, 0);
    6657
    67         foreach (ISymbol parent in originalGrammar.Symbols) {
    68           if (parent is StartSymbol || parent is ProgramRootSymbol) continue;
    69           if (originalGrammar.IsAllowedChildSymbol(parent, pair.CutPoint.Child.Symbol))
    70             grammar.AddAllowedChildSymbol(parent, argSymbol);
     58        foreach (var symb in grammar.Symbols) {
     59          if (symb is ProgramRootSymbol || symb is StartSymbol) continue;
     60          if (originalGrammar.IsAllowedChildSymbol(symb, pair.CutPoint.Child.Symbol))
     61            grammar.AddAllowedChildSymbol(symb, argSymbol);
    7162          else {
    72             for (int i = 0; i < originalGrammar.GetMaximumSubtreeCount(parent); i++) {
    73               if (originalGrammar.IsAllowedChildSymbol(parent, pair.CutPoint.Child.Symbol, i))
    74                 grammar.AddAllowedChildSymbol(parent, argSymbol, i);
     63            for (int i = 0; i < grammar.GetMaximumSubtreeCount(symb); i++) {
     64              if (originalGrammar.IsAllowedChildSymbol(symb, pair.CutPoint.Child.Symbol, i))
     65                grammar.AddAllowedChildSymbol(symb, argSymbol, i);
    7566            }
     67          }
     68        }
     69      }
     70    }
     71
     72    internal static void SetAllowedParentSymbols(ISymbolicExpressionTreeGrammar grammar, ISymbol symbol, ISymbol newSymbol) {
     73      foreach (var symb in grammar.Symbols) {
     74        if (symb is ProgramRootSymbol) continue;
     75        if (newSymbol is Argument && symb is StartSymbol) continue;
     76        if (grammar.IsAllowedChildSymbol(symb, symbol))
     77          grammar.AddAllowedChildSymbol(symb, newSymbol);
     78        else {
     79          for (int i = 0; i < grammar.GetMaximumSubtreeCount(symb); i++) {
     80            if (grammar.IsAllowedChildSymbol(symb, symbol, i))
     81              grammar.AddAllowedChildSymbol(symb, newSymbol, i);
    7682          }
    7783        }
  • branches/DataAnalysis Refactoring/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/ArchitectureManipulators/SubroutineDuplicater.cs

    r5733 r5792  
    8989              for (int i = 0; i < subtree.Grammar.GetMaximumSubtreeCount(symbol); i++)
    9090                if (subtree.Grammar.IsAllowedChildSymbol(symbol, matchingInvokeSymbol, i))
    91                   subtree.Grammar.AddAllowedChildSymbol(symbol, matchingInvokeSymbol, i);
     91                  subtree.Grammar.AddAllowedChildSymbol(symbol, invokeSymbol, i);
    9292            }
    9393          }
  • branches/DataAnalysis Refactoring/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/SymbolicExpressionGrammar.cs

    r5742 r5792  
    2020#endregion
    2121
     22using System.Linq;
    2223using HeuristicLab.Common;
    23 using System.Linq;
    2424using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    25 using System.Collections.Generic;
    2625
    2726namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
     
    137136      // ADF branches maxFunctionDefinitions
    138137      for (int argumentIndex = 1; argumentIndex < maximumFunctionDefinitions + 1; argumentIndex++) {
     138        RemoveAllowedChildSymbol(programRootSymbol, defunSymbol, argumentIndex);
    139139        AddAllowedChildSymbol(programRootSymbol, defunSymbol, argumentIndex);
    140140      }
  • branches/DataAnalysis Refactoring/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/SymbolicExpressionGrammarBase.cs

    r5712 r5792  
    152152        allowedChildSymbols.Add(parent.Name, childSymbols);
    153153      }
     154      if (childSymbols.Contains(child.Name)) throw new ArgumentException();
    154155      childSymbols.Add(child.Name);
    155156      ClearCaches();
     
    164165      }
    165166
     167      if (IsAllowedChildSymbol(parent, child)) throw new ArgumentException();
     168      if (childSymbols.Contains(child.Name)) throw new ArgumentException();
    166169      childSymbols.Add(child.Name);
    167170      ClearCaches();
     
    169172
    170173    protected void RemoveAllowedChildSymbol(ISymbol parent, ISymbol child) {
    171       allowedChildSymbols[parent.Name].Remove(child.Name);
    172       ClearCaches();
     174      List<string> childSymbols;
     175      if (allowedChildSymbols.TryGetValue(child.Name, out childSymbols)) {
     176        if (allowedChildSymbols[parent.Name].Remove(child.Name))
     177          ClearCaches();
     178      }
    173179    }
    174180
    175181    protected void RemoveAllowedChildSymbol(ISymbol parent, ISymbol child, int argumentIndex) {
    176182      var key = Tuple.Create(parent.Name, argumentIndex);
    177       allowedChildSymbolsPerIndex[key].Remove(child.Name);
    178       ClearCaches();
     183      List<string> childSymbols;
     184      if (allowedChildSymbolsPerIndex.TryGetValue(key, out childSymbols)) {
     185        if (allowedChildSymbolsPerIndex[key].Remove(child.Name))
     186          ClearCaches();
     187      }
    179188    }
    180189
  • branches/DataAnalysis Refactoring/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Tests/AllArchitectureAlteringOperatorsTest.cs

    r5759 r5792  
    3232  public class AllArchitectureAlteringOperatorsTest {
    3333    private const int POPULATION_SIZE = 1000;
    34     private const int N_ITERATIONS = 100;
     34    private const int N_ITERATIONS = 200;
    3535    private const int MAX_TREE_LENGTH = 100;
    3636    private const int MAX_TREE_DEPTH = 10;
     
    9999              par1 = (SymbolicExpressionTree)trees.SelectRandom(random).Clone();
    100100            } while (par0.Length > MAX_TREE_LENGTH || par1.Length > MAX_TREE_LENGTH);
    101             newTrees.Add(SubtreeCrossover.Cross(random, par0, par1, 0.9, MAX_TREE_LENGTH, MAX_TREE_DEPTH));
     101            var newTree = SubtreeCrossover.Cross(random, par0, par1, 0.9, MAX_TREE_LENGTH, MAX_TREE_DEPTH);
     102            Util.IsValid(newTree);
     103            newTrees.Add(newTree);
    102104          }
    103105        }
    104         trees = newTrees;
     106        trees = new List<ISymbolicExpressionTree>(newTrees);
     107        newTrees.Clear();
    105108      }
    106109      var msPerOperation = stopwatch.ElapsedMilliseconds / (double)POPULATION_SIZE / (double)N_ITERATIONS;
  • branches/DataAnalysis Refactoring/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Tests/SubtreeCrossoverTest.cs

    r5733 r5792  
    5252      var grammar = Grammars.CreateArithmeticAndAdfGrammar();
    5353      var random = new MersenneTwister(31415);
    54       List<ISymbolicExpressionTree> crossoverTrees;
    5554      double msPerCrossoverEvent;
    5655
     
    6362      stopwatch.Start();
    6463      for (int gCount = 0; gCount < generations; gCount++) {
    65         var newPopulation = new List<ISymbolicExpressionTree>();
    6664        for (int i = 0; i < POPULATION_SIZE; i++) {
    67           var par0 = (SymbolicExpressionTree)trees.SelectRandom(random).Clone();
    68           var par1 = (SymbolicExpressionTree)trees.SelectRandom(random).Clone();
    69           newPopulation.Add(SubtreeCrossover.Cross(random, par0, par1, 0.9, 100, 10));
     65          var par0 = (ISymbolicExpressionTree)trees.SelectRandom(random).Clone();
     66          var par1 = (ISymbolicExpressionTree)trees.SelectRandom(random).Clone();
     67          SubtreeCrossover.Cross(random, par0, par1, 0.9, 100, 10);
    7068        }
    71         crossoverTrees = newPopulation;
    7269      }
    7370      stopwatch.Stop();
  • branches/DataAnalysis Refactoring/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Tests/Util.cs

    r5733 r5792  
    141141
    142142      }
     143
    143144      foreach (var subtree in tree.Root.Subtrees) {
    144145        Assert.AreNotSame(subtree.Grammar, tree.Root.Grammar);
     
    159160        }
    160161      }
     162
     163      foreach (var symbol in grammar.ModifyableSymbols) {
     164        //check if ever symbol has at least on
     165        for (int i = 0; i < grammar.GetMaximumSubtreeCount(symbol); i++)
     166          Assert.IsTrue(grammar.GetAllowedChildSymbols(symbol, i).Any());
     167
     168        //if (symbol is ProgramRootSymbol) continue;
     169        ////check if symbol is allowed as at least one child symbol
     170        //bool result = false;
     171        //foreach (var parentSymbol in grammar.Symbols) {
     172        //  if (result) break;
     173        //  for (int i = 0; i < grammar.GetMaximumSubtreeCount(parentSymbol); i++)
     174        //    result = result || grammar.IsAllowedChildSymbol(parentSymbol, symbol, i);
     175        //}
     176        //Assert.IsTrue(result);
     177
     178      }
    161179    }
    162180
  • branches/DataAnalysis Refactoring/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tests/SymbolicDataAnalysisExpressionTreeInterpreterTest.cs

    r5686 r5792  
    7070      SymbolicDataAnalysisExpressionTreeInterpreter interpreter = new SymbolicDataAnalysisExpressionTreeInterpreter();
    7171      double nodesPerSec = Util.CalculateEvaluatedNodesPerSec(randomTrees, interpreter, dataset, 3);
    72       Assert.IsTrue(nodesPerSec > 15.0e6); // evaluated nodes per seconds must be larger than 15mNodes/sec
     72      Assert.IsTrue(nodesPerSec > 12.5e6); // evaluated nodes per seconds must be larger than 15mNodes/sec
    7373    }
    7474
     
    8989      SymbolicDataAnalysisExpressionTreeInterpreter interpreter = new SymbolicDataAnalysisExpressionTreeInterpreter();
    9090      double nodesPerSec = Util.CalculateEvaluatedNodesPerSec(randomTrees, interpreter, dataset, 3);
    91       Assert.IsTrue(nodesPerSec > 15.0e6); // evaluated nodes per seconds must be larger than 15mNodes/sec
     91      Assert.IsTrue(nodesPerSec > 12.5e6); // evaluated nodes per seconds must be larger than 15mNodes/sec
    9292    }
    9393
Note: See TracChangeset for help on using the changeset viewer.