Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
04/09/10 17:28:32 (15 years ago)
Author:
gkronber
Message:

Added first version of architecture altering operators for ADFs. #290 (Implement ADFs)

Location:
trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3
Files:
26 added
1 deleted
15 edited

Legend:

Unmodified
Added
Removed

  • TabularUnified trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Creators/ProbabilisticTreeCreator.cs

    r3270 r3294  
    3737
    3838    protected override SymbolicExpressionTree Create(IRandom random, ISymbolicExpressionGrammar grammar, IntValue maxTreeSize, IntValue maxTreeHeight) {
    39       return Apply(random, grammar, maxTreeSize.Value, maxTreeHeight.Value);
     39      return Create(random, grammar, maxTreeSize.Value, maxTreeHeight.Value);
    4040    }
    4141
    42     public SymbolicExpressionTree Apply(IRandom random, ISymbolicExpressionGrammar grammar, int maxTreeSize, int maxTreeHeight) {
     42    public static SymbolicExpressionTree Create(IRandom random, ISymbolicExpressionGrammar grammar, int maxTreeSize, int maxTreeHeight) {
    4343      // tree size is limited by the grammar and by the explicit size constraints
    44       int allowedMinSize = grammar.MinimalExpressionLength(grammar.StartSymbol);
    45       int allowedMaxSize = Math.Min(maxTreeSize, grammar.MaximalExpressionLength(grammar.StartSymbol));
     44      int allowedMinSize = grammar.GetMinExpressionLength(grammar.StartSymbol);
     45      int allowedMaxSize = Math.Min(maxTreeSize, grammar.GetMaxExpressionLength(grammar.StartSymbol));
    4646      // select a target tree size uniformly in the possible range (as determined by explicit limits and limits of the grammar)
    4747      int treeSize = random.Next(allowedMinSize, allowedMaxSize);
    … …  
    4949      do {
    5050        try {
    51           tree.Root = PTC2(random, grammar, grammar.StartSymbol, treeSize + 1, maxTreeHeight + 1);
     51          tree.Root = grammar.ProgramRootSymbol.CreateTreeNode();
     52          tree.Root.AddSubTree(PTC2(random, grammar, grammar.StartSymbol, treeSize + 1, maxTreeHeight + 1));
    5253        }
    5354        catch (ArgumentException) {
    … …  
    5556          treeSize = random.Next(allowedMinSize, allowedMaxSize);
    5657        }
    57       } while (tree.Root == null || tree.Size > maxTreeSize || tree.Height > maxTreeHeight);
     58      } while (tree.Root.SubTrees.Count == 0 || tree.Size > maxTreeSize || tree.Height > maxTreeHeight);
     59      System.Diagnostics.Debug.Assert(grammar.IsValidExpression(tree));
    5860      return tree;
    5961    }
    6062
    61     private Symbol SelectRandomSymbol(IRandom random, IEnumerable<Symbol> symbols) {
     63    private static Symbol SelectRandomSymbol(IRandom random, IEnumerable<Symbol> symbols) {
    6264      var symbolList = symbols.ToList();
    63       var ticketsSum = symbolList.Select(x => x.Tickets.Value).Sum();
     65      var ticketsSum = symbolList.Select(x => x.InitialFrequency).Sum();
    6466      var r = random.NextDouble() * ticketsSum;
    6567      double aggregatedTickets = 0;
    6668      for (int i = 0; i < symbolList.Count; i++) {
    67         aggregatedTickets += symbolList[i].Tickets.Value;
     69        aggregatedTickets += symbolList[i].InitialFrequency;
    6870        if (aggregatedTickets >= r) {
    6971          return symbolList[i];
    … …  
    7577
    7678
    77     private SymbolicExpressionTreeNode PTC2(IRandom random, ISymbolicExpressionGrammar grammar, Symbol rootSymbol, int size, int maxDepth) {
     79    public static SymbolicExpressionTreeNode PTC2(IRandom random, ISymbolicExpressionGrammar grammar, Symbol rootSymbol, int size, int maxDepth) {
    7880      SymbolicExpressionTreeNode root = rootSymbol.CreateTreeNode();
    7981      if (size <= 1 || maxDepth <= 1) return root;
    80       List<object[]> list = new List<object[]>();
     82      List<object[]> extensionPoints = new List<object[]>();
    8183      int currentSize = 1;
    82       int totalListMinSize = grammar.MinimalExpressionLength(rootSymbol) - 1;
     84      int totalListMinSize = grammar.GetMinExpressionLength(rootSymbol) - 1;
    8385
    8486      int actualArity = SampleArity(random, grammar, rootSymbol, size);
    … …  
    8688        // insert a dummy sub-tree and add the pending extension to the list
    8789        root.AddSubTree(null);
    88         list.Add(new object[] { root, i, 2 });
     90        extensionPoints.Add(new object[] { root, i, 2 });
    8991      }
    9092
    9193      // while there are pending extension points and we have not reached the limit of adding new extension points
    92       while (list.Count > 0 && totalListMinSize + currentSize < size) {
    93         int randomIndex = random.Next(list.Count);
    94         object[] nextExtension = list[randomIndex];
    95         list.RemoveAt(randomIndex);
     94      while (extensionPoints.Count > 0 && totalListMinSize + currentSize < size) {
     95        int randomIndex = random.Next(extensionPoints.Count);
     96        object[] nextExtension = extensionPoints[randomIndex];
     97        extensionPoints.RemoveAt(randomIndex);
    9698        SymbolicExpressionTreeNode parent = (SymbolicExpressionTreeNode)nextExtension[0];
    9799        int argumentIndex = (int)nextExtension[1];
    98100        int extensionDepth = (int)nextExtension[2];
    99         if (extensionDepth + grammar.MinimalExpressionDepth(parent.Symbol) >= maxDepth) {
     101        if (extensionDepth + grammar.GetMinExpressionDepth(parent.Symbol) >= maxDepth) {
    100102          parent.RemoveSubTree(argumentIndex);
    101           SymbolicExpressionTreeNode branch = CreateMinimalTree(random, grammar, grammar.AllowedSymbols(parent.Symbol, argumentIndex));
     103          SymbolicExpressionTreeNode branch = CreateMinimalTree(random, grammar, grammar.GetAllowedSymbols(parent.Symbol, argumentIndex));
    102104          parent.InsertSubTree(argumentIndex, branch); // insert a smallest possible tree
    103105          currentSize += branch.GetSize();
    104106          totalListMinSize -= branch.GetSize();
    105107        } else {
    106           var allowedSubFunctions = from s in grammar.AllowedSymbols(parent.Symbol, argumentIndex)
    107                                     where grammar.MinimalExpressionDepth(parent.Symbol) + extensionDepth - 1 < maxDepth
    108                                     where grammar.MaximalExpressionLength(s) > size - totalListMinSize - currentSize ||
     108          var allowedSubFunctions = from s in grammar.GetAllowedSymbols(parent.Symbol, argumentIndex)
     109                                    where grammar.GetMinExpressionDepth(parent.Symbol) + extensionDepth - 1 < maxDepth
     110                                    where grammar.GetMaxExpressionLength(s) > size - totalListMinSize - currentSize ||
    109111                                          totalListMinSize + currentSize >= size * 0.9 // if the necessary size is almost reached then also allow
    110112                                    // terminals or terminal-branches
    … …  
    121123            // insert a dummy sub-tree and add the pending extension to the list
    122124            newTree.AddSubTree(null);
    123             list.Add(new object[] { newTree, i, extensionDepth + 1 });
     125            extensionPoints.Add(new object[] { newTree, i, extensionDepth + 1 });
    124126          }
    125           totalListMinSize += grammar.MinimalExpressionLength(selectedSymbol);
     127          totalListMinSize += grammar.GetMinExpressionLength(selectedSymbol);
    126128        }
    127129      }
    128130      // fill all pending extension points
    129       while (list.Count > 0) {
    130         int randomIndex = random.Next(list.Count);
    131         object[] nextExtension = list[randomIndex];
    132         list.RemoveAt(randomIndex);
     131      while (extensionPoints.Count > 0) {
     132        int randomIndex = random.Next(extensionPoints.Count);
     133        object[] nextExtension = extensionPoints[randomIndex];
     134        extensionPoints.RemoveAt(randomIndex);
    133135        SymbolicExpressionTreeNode parent = (SymbolicExpressionTreeNode)nextExtension[0];
    134136        int a = (int)nextExtension[1];
    … …  
    136138        parent.RemoveSubTree(a);
    137139        parent.InsertSubTree(a,
    138           CreateMinimalTree(random, grammar, grammar.AllowedSymbols(parent.Symbol, a))); // append a tree with minimal possible height
     140          CreateMinimalTree(random, grammar, grammar.GetAllowedSymbols(parent.Symbol, a))); // append a tree with minimal possible height
    139141      }
    140142      return root;
    141143    }
    142144
    143     private int SampleArity(IRandom random, ISymbolicExpressionGrammar grammar, Symbol symbol, int targetSize) {
     145    private static int SampleArity(IRandom random, ISymbolicExpressionGrammar grammar, Symbol symbol, int targetSize) {
    144146      // select actualArity randomly with the constraint that the sub-trees in the minimal arity can become large enough
    145       int minArity = grammar.MinSubTrees(symbol);
    146       int maxArity = grammar.MaxSubTrees(symbol);
     147      int minArity = grammar.GetMinSubTreeCount(symbol);
     148      int maxArity = grammar.GetMaxSubTreeCount(symbol);
    147149      if (maxArity > targetSize) {
    148150        maxArity = targetSize;
    … …  
    152154      long aggregatedLongestExpressionLength = 0;
    153155      for (int i = 0; i < maxArity; i++) {
    154         aggregatedLongestExpressionLength += (from s in grammar.AllowedSymbols(symbol, i)
    155                                               select grammar.MaximalExpressionLength(s)).Max();
     156        aggregatedLongestExpressionLength += (from s in grammar.GetAllowedSymbols(symbol, i)
     157                                              select grammar.GetMaxExpressionLength(s)).Max();
    156158        if (aggregatedLongestExpressionLength < targetSize) minArity = i;
    157159        else break;
    … …  
    162164      long aggregatedShortestExpressionLength = 0;
    163165      for (int i = 0; i < maxArity; i++) {
    164         aggregatedShortestExpressionLength += (from s in grammar.AllowedSymbols(symbol, i)
    165                                                select grammar.MinimalExpressionLength(s)).Min();
     166        aggregatedShortestExpressionLength += (from s in grammar.GetAllowedSymbols(symbol, i)
     167                                               select grammar.GetMinExpressionLength(s)).Min();
    166168        if (aggregatedShortestExpressionLength > targetSize) {
    167169          maxArity = i;
    … …  
    173175    }
    174176
    175     private SymbolicExpressionTreeNode CreateMinimalTree(IRandom random, ISymbolicExpressionGrammar grammar, IEnumerable<Symbol> symbols) {
     177    private static SymbolicExpressionTreeNode CreateMinimalTree(IRandom random, ISymbolicExpressionGrammar grammar, IEnumerable<Symbol> symbols) {
    176178      // determine possible symbols that will lead to the smallest possible tree
    177179      var possibleSymbols = (from s in symbols
    178                              group s by grammar.MinimalExpressionLength(s) into g
     180                             group s by grammar.GetMinExpressionLength(s) into g
    179181                             orderby g.Key
    180182                             select g).First();
    … …  
    182184      // build minimal tree by recursive application
    183185      var tree = selectedSymbol.CreateTreeNode();
    184       for (int i = 0; i < grammar.MinSubTrees(selectedSymbol); i++)
    185         tree.AddSubTree(CreateMinimalTree(random, grammar, grammar.AllowedSymbols(selectedSymbol, i)));
     186      for (int i = 0; i < grammar.GetMinSubTreeCount(selectedSymbol); i++)
     187        tree.AddSubTree(CreateMinimalTree(random, grammar, grammar.GetAllowedSymbols(selectedSymbol, i)));
    186188      return tree;
    187189    }

  • TabularUnified trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Crossovers/SubtreeCrossover.cs

    r3237 r3294  
    2727using System;
    2828using HeuristicLab.Parameters;
     29using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.GeneralSymbols;
    2930namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
    3031
    … …  
    3940  [StorableClass]
    4041  public class SubtreeCrossover : SymbolicExpressionTreeCrossover {
    41     private const int MAX_TRIES = 100;
    42 
    4342    public IValueLookupParameter<PercentValue> InternalCrossoverPointProbabilityParameter {
    4443      get { return (IValueLookupParameter<PercentValue>)Parameters["InternalCrossoverPointProbability"]; }
    … …  
    5251    protected override SymbolicExpressionTree Cross(IRandom random, ISymbolicExpressionGrammar grammar,
    5352      SymbolicExpressionTree parent0, SymbolicExpressionTree parent1,
    54       IntValue maxTreeSize, IntValue maxTreeHeight) {
    55       return Apply(random, grammar, parent0, parent1, InternalCrossoverPointProbabilityParameter.ActualValue.Value, maxTreeSize.Value, maxTreeHeight.Value);
     53      IntValue maxTreeSize, IntValue maxTreeHeight, out bool success) {
     54      return Cross(random, grammar, parent0, parent1, InternalCrossoverPointProbabilityParameter.ActualValue.Value, maxTreeSize.Value, maxTreeHeight.Value, out success);
    5655    }
    5756
    58     public static SymbolicExpressionTree Apply(IRandom random, ISymbolicExpressionGrammar grammar,
     57    public static SymbolicExpressionTree Cross(IRandom random, ISymbolicExpressionGrammar grammar,
    5958      SymbolicExpressionTree parent0, SymbolicExpressionTree parent1,
    60       double internalCrossoverPointProbability, int maxTreeSize, int maxTreeHeight) {
    61       int tries = 0;
    62       while (tries++ < MAX_TRIES) {
    63         // select a random crossover point in the first parent
    64         SymbolicExpressionTreeNode crossoverPoint0;
    65         int replacedSubtreeIndex;
    66         SelectCrossoverPoint(random, parent0, internalCrossoverPointProbability, out crossoverPoint0, out replacedSubtreeIndex);
     59      double internalCrossoverPointProbability, int maxTreeSize, int maxTreeHeight, out bool success) {
     60      // select a random crossover point in the first parent
     61      SymbolicExpressionTreeNode crossoverPoint0;
     62      int replacedSubtreeIndex;
     63      SelectCrossoverPoint(random, parent0, internalCrossoverPointProbability, out crossoverPoint0, out replacedSubtreeIndex);
    6764
    68         // calculate the max size and height that the inserted branch can have
    69         int maxInsertedBranchSize = maxTreeSize - (parent0.Size - crossoverPoint0.SubTrees[replacedSubtreeIndex].GetSize());
    70         int maxInsertedBranchHeight = maxTreeHeight - GetBranchLevel(parent0.Root, crossoverPoint0);
     65      // calculate the max size and height that the inserted branch can have
     66      int maxInsertedBranchSize = maxTreeSize - (parent0.Size - crossoverPoint0.SubTrees[replacedSubtreeIndex].GetSize());
     67      int maxInsertedBranchHeight = maxTreeHeight - GetBranchLevel(parent0.Root, crossoverPoint0);
    7168
    72         var allowedBranches = from branch in IterateNodes(parent1.Root)
    73                               where branch.GetSize() < maxInsertedBranchSize
    74                               where branch.GetHeight() < maxInsertedBranchHeight
    75                               where grammar.AllowedSymbols(crossoverPoint0.Symbol, replacedSubtreeIndex).Contains(branch.Symbol)
    76                               select branch;
     69      var allowedBranches = from branch in IterateNodes(parent1.Root)
     70                            where branch.GetSize() < maxInsertedBranchSize
     71                            where branch.GetHeight() < maxInsertedBranchHeight
     72                            where grammar.GetAllowedSymbols(crossoverPoint0.Symbol, replacedSubtreeIndex).Contains(branch.Symbol)
     73                            where IsMatchingPointType(parent0, crossoverPoint0, branch)
     74                            select branch;
    7775
    78         if (allowedBranches.Count() > 0) {
    79           var selectedBranch = SelectRandomBranch(random, allowedBranches, internalCrossoverPointProbability);
     76      if (allowedBranches.Count() > 0) {
     77        var selectedBranch = SelectRandomBranch(random, allowedBranches, internalCrossoverPointProbability);
    8078
    81           // manipulate the tree of parent0 in place
    82           // replace the branch in tree0 with the selected branch from tree1
    83           crossoverPoint0.RemoveSubTree(replacedSubtreeIndex);
    84           crossoverPoint0.InsertSubTree(replacedSubtreeIndex, selectedBranch);
    85           return parent0;
    86         }
     79        // manipulate the tree of parent0 in place
     80        // replace the branch in tree0 with the selected branch from tree1
     81        crossoverPoint0.RemoveSubTree(replacedSubtreeIndex);
     82        crossoverPoint0.InsertSubTree(replacedSubtreeIndex, selectedBranch);
     83        success = true;
     84        return parent0;
    8785      }
    8886
    89       // TODO: we should have a way to track the number of failed crossover attempts
    90       // for now just return the first parent unchanged
     87      success = false;
    9188      return parent0;
     89    }
     90
     91    private static bool IsMatchingPointType(SymbolicExpressionTree tree, SymbolicExpressionTreeNode parent, SymbolicExpressionTreeNode newBranch) {
     92      var functionCalls = (from node in IterateNodes(newBranch)
     93                           let invokeNode = node as InvokeFunctionTreeNode
     94                           let argNode = node as ArgumentTreeNode
     95                           where invokeNode != null || argNode != null
     96                           let name = invokeNode != null ? invokeNode.InvokedFunctionName : "ARG" + argNode.ArgumentIndex
     97                           let argCount = invokeNode != null ? invokeNode.SubTrees.Count : 0
     98                           select new { FunctionName = name, FunctionArgumentCount = argCount }).Distinct();
     99      var definingBranch = GetDefiningBranch(tree, parent);
     100      if (definingBranch == null) return false;
     101      foreach (var functionCall in functionCalls) {
     102        if (!definingBranch.DynamicSymbols.Contains(functionCall.FunctionName) ||
     103          definingBranch.GetDynamicSymbolArgumentCount(functionCall.FunctionName) != functionCall.FunctionArgumentCount)
     104          return false;
     105      }
     106      return true;
     107    }
     108
     109    private static SymbolicExpressionTreeNode GetDefiningBranch(SymbolicExpressionTree tree, SymbolicExpressionTreeNode parent) {
     110      foreach (var treeNode in tree.Root.SubTrees) {
     111        if (IterateNodes(treeNode).Contains(parent)) return treeNode;
     112      }
     113      return null;
    92114    }
    93115
    … …  
    95117      var crossoverPoints = from branch in IterateNodes(parent0.Root)
    96118                            where branch.SubTrees.Count > 0
     119                            where !(branch.Symbol is ProgramRootSymbol)
    97120                            from index in Enumerable.Range(0, branch.SubTrees.Count)
    98121                            let p = new { CrossoverPoint = branch, SubtreeIndex = index, IsLeaf = branch.SubTrees[index].SubTrees.Count == 0 }
    … …  
    101124                                     where !p.IsLeaf
    102125                                     select p).ToList();
    103       // select internal crossover point or leaf
    104       if (random.NextDouble() < internalNodeProbability && internalCrossoverPoints.Count > 0) {
     126      var leafCrossoverPoints = (from p in crossoverPoints
     127                                 where p.IsLeaf
     128                                 select p).ToList();
     129      if (internalCrossoverPoints.Count == 0) {
     130        var selectedCrossoverPoint = leafCrossoverPoints[random.Next(leafCrossoverPoints.Count)];
     131        crossoverPoint = selectedCrossoverPoint.CrossoverPoint;
     132        subtreeIndex = selectedCrossoverPoint.SubtreeIndex;
     133      } else if (leafCrossoverPoints.Count == 0) {
     134        var selectedCrossoverPoint = internalCrossoverPoints[random.Next(internalCrossoverPoints.Count)];
     135        crossoverPoint = selectedCrossoverPoint.CrossoverPoint;
     136        subtreeIndex = selectedCrossoverPoint.SubtreeIndex;
     137      } else if (random.NextDouble() < internalNodeProbability && internalCrossoverPoints.Count > 0) {
     138        // select internal crossover point or leaf
    105139        var selectedCrossoverPoint = internalCrossoverPoints[random.Next(internalCrossoverPoints.Count)];
    106140        crossoverPoint = selectedCrossoverPoint.CrossoverPoint;
    107141        subtreeIndex = selectedCrossoverPoint.SubtreeIndex;
    108142      } else {
    109         var leafCrossoverPoints = (from p in crossoverPoints
    110                                    where p.IsLeaf
    111                                    select p).ToList();
    112143        var selectedCrossoverPoint = leafCrossoverPoints[random.Next(leafCrossoverPoints.Count)];
    113144        crossoverPoint = selectedCrossoverPoint.CrossoverPoint;
    … …  
    125156                                     from branch in g
    126157                                     select branch).ToList();
    127       if (random.NextDouble() < internalNodeProbability && allowedInternalBranches.Count > 0) {
     158      var allowedLeafBranches = (from g in groupedBranches
     159                                 where g.Key == 0
     160                                 from leaf in g
     161                                 select leaf).ToList();
     162      if (allowedInternalBranches.Count == 0) {
     163        return allowedLeafBranches[random.Next(allowedLeafBranches.Count)];
     164      } else if (allowedLeafBranches.Count == 0) {
     165        return allowedInternalBranches[random.Next(allowedInternalBranches.Count)];
     166      } else if (random.NextDouble() < internalNodeProbability) {
     167        // when leaf and internal nodes are possible then choose either a leaf or internal node with internalNodeProbability
    128168        return allowedInternalBranches[random.Next(allowedInternalBranches.Count)];
    129169      } else {
    130         var allowedLeafBranches = (from g in groupedBranches
    131                                    where g.Key == 0
    132                                    from leaf in g
    133                                    select leaf).ToList();
    134170        return allowedLeafBranches[random.Next(allowedLeafBranches.Count)];
    135171      }

  • TabularUnified trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.3.csproj

    r3256 r3294  
    8383  </ItemGroup>
    8484  <ItemGroup>
     85    <Compile Include="ArchitectureAlteringOperators\ArgumentDuplicater.cs" />
     86    <Compile Include="ArchitectureAlteringOperators\ArgumentCreater.cs" />
     87    <Compile Include="ArchitectureAlteringOperators\ArgumentDeleter.cs" />
     88    <Compile Include="ArchitectureAlteringOperators\RandomArchitectureAlteringOperator.cs" />
     89    <Compile Include="ArchitectureAlteringOperators\SubroutineDeleter.cs" />
     90    <Compile Include="ArchitectureAlteringOperators\SubroutineCreater.cs">
     91      <SubType>Code</SubType>
     92    </Compile>
     93    <Compile Include="ArchitectureAlteringOperators\SubroutineDuplicater.cs">
     94      <SubType>Code</SubType>
     95    </Compile>
     96    <Compile Include="DefaultSymbolicExpressionGrammar.cs">
     97      <SubType>Code</SubType>
     98    </Compile>
     99    <Compile Include="SymbolicExpressionTreeArchitectureAlteringOperator.cs" />
     100    <Compile Include="SymbolicExpressionTreeOperator.cs" />
     101    <Compile Include="Instruction.cs" />
     102    <Compile Include="SymbolicExpressionTreeCompiler.cs" />
     103    <Compile Include="SymbolicExpressionTreeManipulator.cs" />
    85104    <Compile Include="SymbolicExpressionTreeTerminalNode.cs" />
    86105    <Compile Include="Crossovers\SubtreeCrossover.cs" />
    … …  
    89108    <Compile Include="HeuristicLabEncodingsSymbolicExpressionTreeEncodingPlugin.cs" />
    90109    <Compile Include="Interfaces\ISymbolicExpressionTreeOperator.cs" />
    91     <Compile Include="SymbolicExpressionGrammar.cs" />
    92110    <Compile Include="SymbolicExpressionTreeCreator.cs" />
    93111    <Compile Include="SymbolicExpressionTree.cs" />
    … …  
    97115    <Compile Include="SymbolicExpressionTreeNode.cs" />
    98116    <Compile Include="Symbols\Addition.cs" />
    99     <Compile Include="Symbols\Prog.cs" />
    100     <Compile Include="GeneralSymbolicExpressionTreeEvaluator.cs" />
     117    <Compile Include="Symbols\Argument.cs" />
     118    <Compile Include="Symbols\ArgumentTreeNode.cs" />
    101119    <Compile Include="Symbols\StartSymbol.cs" />
     120    <Compile Include="Symbols\InvokeFunction.cs" />
     121    <Compile Include="Symbols\InvokeFunctionTreeNode.cs" />
     122    <Compile Include="Symbols\DefunTreeNode.cs" />
     123    <Compile Include="Symbols\Defun.cs" />
     124    <Compile Include="Symbols\ProgramRootSymbol.cs" />
    102125    <Compile Include="Symbols\Division.cs" />
    103126    <Compile Include="Symbols\Multiplication.cs" />
    104127    <Compile Include="Symbols\Subtraction.cs" />
     128    <Compile Include="Symbols\Values.cs">
     129      <SubType>Code</SubType>
     130    </Compile>
     131    <Compile Include="Symbols\ValuesTreeNode.cs">
     132      <SubType>Code</SubType>
     133    </Compile>
    105134  </ItemGroup>
    106135  <ItemGroup>

  • TabularUnified trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Interfaces/ISymbolicExpressionGrammar.cs

    r3237 r3294  
    3131  public interface ISymbolicExpressionGrammar : IItem {
    3232    Symbol StartSymbol { get; }
    33     // IEnumerable<Symbol> Symbols { get; }
    34 
    35     // void AddSymbol(Symbol symbol);
    36     // void RemoveSymbol(Symbol symbol);
    37 
    38     IEnumerable<Symbol> AllowedSymbols(Symbol parent, int argumentIndex);
    39     int MinimalExpressionLength(Symbol start);
    40     int MaximalExpressionLength(Symbol start);
    41     int MinimalExpressionDepth(Symbol start);
    42     int MinSubTrees(Symbol start);
    43     int MaxSubTrees(Symbol start);
     33    Symbol ProgramRootSymbol { get; }
     34    IEnumerable<Symbol> GetAllowedSymbols(Symbol parent, int argumentIndex);
     35    int GetMinExpressionLength(Symbol start);
     36    int GetMaxExpressionLength(Symbol start);
     37    int GetMinExpressionDepth(Symbol start);
     38    int GetMinSubTreeCount(Symbol start);
     39    int GetMaxSubTreeCount(Symbol start);
    4440
    4541    bool IsValidExpression(SymbolicExpressionTree expression);

  • TabularUnified trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Symbol.cs

    r3269 r3294  
    3232  [StorableClass]
    3333  [Item("Symbol", "Represents a symbol in a symbolic function tree.")]
    34   public abstract class Symbol : ParameterizedNamedItem {
    35     #region Parameter Properties
    36     public IValueParameter<DoubleValue> TicketsParameter {
    37       get { return (IValueParameter<DoubleValue>)Parameters["Tickets"]; }
    38     }
    39     #endregion
    40 
     34  public abstract class Symbol : NamedItem {
    4135    #region Properties
    42     public DoubleValue Tickets {
    43       get { return TicketsParameter.Value; }
     36    private double initialFrequency;
     37    public double InitialFrequency {
     38      get { return initialFrequency; }
    4439      set {
    45         if (value.Value < 0.0) throw new ArgumentException("Number of tickets must be positive");
    46         TicketsParameter.Value = value;
     40        if (value < 0.0) throw new ArgumentException("InitialFrequency must be positive");
     41        initialFrequency = value;
    4742      }
    4843    }
    … …  
    5146    protected Symbol()
    5247      : base() {
    53       Parameters.Add(new ValueParameter<DoubleValue>("Tickets", new DoubleValue(1.0)));
     48      this.name = ItemName;
     49      this.description = ItemDescription;
     50      initialFrequency = 1.0;
    5451    }
    5552

  • TabularUnified trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/SymbolicExpressionTree.cs

    r3252 r3294  
    3232  [StorableClass]
    3333  [Item("SymbolicExpressionTree", "Represents a symbolic expression tree.")]
    34   public class SymbolicExpressionTree : Item {   
     34  public class SymbolicExpressionTree : Item {
    3535    [Storable]
    3636    private SymbolicExpressionTreeNode root;
    … …  
    4646    }
    4747
     48    public SymbolicExpressionTreeNode ResultProducingExpression {
     49      get { return root.SubTrees[0].SubTrees[0]; }
     50    }
     51
     52    [Storable]
     53    private Dictionary<int, IEnumerable<string>> allowedFunctionsInBranch;
     54
    4855    public int Size {
    4956      get {
    … …  
    5865    }
    5966
    60     public SymbolicExpressionTree() : base() { }
     67    public SymbolicExpressionTree()
     68      : base() {
     69      allowedFunctionsInBranch = new Dictionary<int, IEnumerable<string>>();
     70    }
    6171
    62     public SymbolicExpressionTree(SymbolicExpressionTreeNode root) : base() { }
     72    public SymbolicExpressionTree(SymbolicExpressionTreeNode root)
     73      : base() {
     74      allowedFunctionsInBranch = new Dictionary<int, IEnumerable<string>>();
     75    }
    6376
    6477    public IEnumerable<SymbolicExpressionTreeNode> IterateNodesPrefix() {
    … …  
    87100      cloner.RegisterClonedObject(this, clone);
    88101      clone.root = (SymbolicExpressionTreeNode)this.root.Clone();
     102      clone.allowedFunctionsInBranch = new Dictionary<int, IEnumerable<string>>(allowedFunctionsInBranch);
    89103      return clone;
    90104    }

  • TabularUnified trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/SymbolicExpressionTreeCreator.cs

    r3269 r3294  
    3434  [Item("SymbolicExpressionTreeCreator", "A base class for operators creating symbolic expression trees.")]
    3535  [StorableClass]
    36   public abstract class SymbolicExpressionTreeCreator : SingleSuccessorOperator, ISolutionCreator, IStochasticOperator, ISymbolicExpressionTreeOperator {
    37     private const string RandomParameterName = "Random";
    38     private const string SymbolicExpressionTreeParameterName = "SymbolicExpressionTree";
    39     private const string MaxTreeSizeParameterName = "MaxTreeSize";
    40     private const string MaxTreeHeightParameterName = "MaxTreeHeight";
    41     private const string SymbolicExpressionGrammarParameterName = "SymbolicExpressionGrammar";
    42 
    43     public override bool CanChangeName {
    44       get { return false; }
    45     }
    46 
    47     public ILookupParameter<IRandom> RandomParameter {
    48       get { return (LookupParameter<IRandom>)Parameters[RandomParameterName]; }
    49     }
    50     public ILookupParameter<SymbolicExpressionTree> SymbolicExpressionTreeParameter {
    51       get { return (ILookupParameter<SymbolicExpressionTree>)Parameters[SymbolicExpressionTreeParameterName]; }
    52     }
    53     public IValueLookupParameter<IntValue> MaxTreeSizeParameter {
    54       get { return (IValueLookupParameter<IntValue>)Parameters[MaxTreeSizeParameterName]; }
    55     }
    56     public IValueLookupParameter<IntValue> MaxTreeHeightParameter {
    57       get { return (IValueLookupParameter<IntValue>)Parameters[MaxTreeHeightParameterName]; }
    58     }
    59     public ILookupParameter<ISymbolicExpressionGrammar> SymbolicExpressionGrammarParameter {
    60       get { return (ILookupParameter<ISymbolicExpressionGrammar>)Parameters[SymbolicExpressionGrammarParameterName]; }
    61     }
    62 
     36  public abstract class SymbolicExpressionTreeCreator : SymbolicExpressionTreeOperator, ISolutionCreator {
    6337    protected SymbolicExpressionTreeCreator()
    6438      : base() {
    65       Parameters.Add(new LookupParameter<IRandom>(RandomParameterName, "The pseudo random number generator which should be used for stochastic solution creation operators."));
    66       Parameters.Add(new LookupParameter<SymbolicExpressionTree>(SymbolicExpressionTreeParameterName, "The symbolic expression tree that should be initialized."));
    67       Parameters.Add(new ValueLookupParameter<IntValue>(MaxTreeSizeParameterName, "The maximal size (number of nodes) of the symbolic expression tree that should be initialized."));
    68       Parameters.Add(new ValueLookupParameter<IntValue>(MaxTreeHeightParameterName, "The maximal height of the symbolic expression tree that should be initialized (a tree with one node has height = 0)."));
    69       Parameters.Add(new LookupParameter<ISymbolicExpressionGrammar>(SymbolicExpressionGrammarParameterName, "The grammar that defines the allowed symbols and syntax of the symbolic expression trees."));
    7039    }
    7140

  • TabularUnified trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/SymbolicExpressionTreeCrossover.cs

    r3239 r3294  
    3535  [Item("SymbolicExpressionTreeCrossover", "A base class for operators that perform a crossover of symbolic expression trees.")]
    3636  [StorableClass]
    37   public abstract class SymbolicExpressionTreeCrossover : SingleSuccessorOperator, ICrossover, IStochasticOperator, ISymbolicExpressionTreeOperator {
    38     public override bool CanChangeName {
    39       get { return false; }
     37  public abstract class SymbolicExpressionTreeCrossover : SymbolicExpressionTreeOperator, ICrossover {
     38    private const string ParentsParameterName = "Parents";
     39    private const string ChildParameterName = "Child";
     40    private const string FailedCrossoverEventsParameterName = "FailedCrossoverEvents";
     41    public ILookupParameter<ItemArray<SymbolicExpressionTree>> ParentsParameter {
     42      get { return (SubScopesLookupParameter<SymbolicExpressionTree>)Parameters[ParentsParameterName]; }
     43    }
     44    public ILookupParameter<SymbolicExpressionTree> ChildParameter {
     45      get { return (ILookupParameter<SymbolicExpressionTree>)Parameters[ChildParameterName]; }
     46    }
     47    public IValueParameter<IntValue> FailedCrossoverEventsParameter {
     48      get { return (ValueParameter<IntValue>)Parameters[FailedCrossoverEventsParameterName]; }
    4049    }
    4150
    42     public ILookupParameter<IRandom> RandomParameter {
    43       get { return (LookupParameter<IRandom>)Parameters["Random"]; }
     51    public IntValue FailedCrossoverEvents {
     52      get { return FailedCrossoverEventsParameter.Value; }
    4453    }
    45     public ILookupParameter<ItemArray<SymbolicExpressionTree>> ParentsParameter {
    46       get { return (SubScopesLookupParameter<SymbolicExpressionTree>)Parameters["Parents"]; }
    47     }
    48     public ILookupParameter<SymbolicExpressionTree> ChildParameter {
    49       get { return (ILookupParameter<SymbolicExpressionTree>)Parameters["Child"]; }
    50     }
    51     public IValueLookupParameter<IntValue> MaxTreeSizeParameter {
    52       get { return (IValueLookupParameter<IntValue>)Parameters["MaxTreeSize"]; }
    53     }
    54     public IValueLookupParameter<IntValue> MaxTreeHeightParameter {
    55       get { return (IValueLookupParameter<IntValue>)Parameters["MaxTreeHeight"]; }
    56     }
    57     public ILookupParameter<ISymbolicExpressionGrammar> SymbolicExpressionGrammarParameter {
    58       get { return (ILookupParameter<ISymbolicExpressionGrammar>)Parameters["SymbolicExpressionGrammar"]; }
    59     }
    60 
    6154    protected SymbolicExpressionTreeCrossover()
    6255      : base() {
    63       Parameters.Add(new LookupParameter<IRandom>("Random", "The pseudo random number generator which should be used for stochastic crossover operators."));
    64       Parameters.Add(new SubScopesLookupParameter<SymbolicExpressionTree>("Parents", "The parent symbolic expression trees which should be crossed."));
    65       Parameters.Add(new ValueLookupParameter<IntValue>("MaxTreeSize", "The maximal size (number of nodes) of the symbolic expression tree that should be initialized."));
    66       Parameters.Add(new ValueLookupParameter<IntValue>("MaxTreeHeight", "The maximal height of the symbolic expression tree that should be initialized (a tree with one node has height = 0)."));
    67       Parameters.Add(new LookupParameter<ISymbolicExpressionGrammar>("SymbolicExpressionGrammar", "The grammar that defines the allowed symbols and syntax of the symbolic expression trees."));
    68       Parameters.Add(new LookupParameter<SymbolicExpressionTree>("Child", "The child symbolic expression tree resulting from the crossover."));
     56      Parameters.Add(new SubScopesLookupParameter<SymbolicExpressionTree>(ParentsParameterName, "The parent symbolic expression trees which should be crossed."));
     57      Parameters.Add(new LookupParameter<SymbolicExpressionTree>(ChildParameterName, "The child symbolic expression tree resulting from the crossover."));
     58      Parameters.Add(new ValueParameter<IntValue>(FailedCrossoverEventsParameterName, "The number of failed crossover events (child is an exact copy of a parent)", new IntValue()));
    6959    }
    7060
    … …  
    8676      }
    8777
     78      bool success;
    8879      SymbolicExpressionTree result = Cross(random, grammar, parent0, parent1,
    89         MaxTreeSizeParameter.ActualValue, MaxTreeHeightParameter.ActualValue);
     80        MaxTreeSizeParameter.ActualValue, MaxTreeHeightParameter.ActualValue, out success);
     81     
     82      if (!success) FailedCrossoverEvents.Value++;
     83
    9084      Debug.Assert(result.Size <= MaxTreeSizeParameter.ActualValue.Value);
    9185      Debug.Assert(result.Height <= MaxTreeHeightParameter.ActualValue.Value);
    92       Debug.Assert(grammar.IsValidExpression(result));
     86      // Debug.Assert(grammar.IsValidExpression(result));
    9387      ChildParameter.ActualValue = result;
    9488      return base.Apply();
    … …  
    9791    protected abstract SymbolicExpressionTree Cross(IRandom random, ISymbolicExpressionGrammar grammar,
    9892      SymbolicExpressionTree parent0, SymbolicExpressionTree parent1,
    99       IntValue maxTreeSize, IntValue maxTreeHeight);
     93      IntValue maxTreeSize, IntValue maxTreeHeight, out bool success);
    10094  }
    10195}

  • TabularUnified trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/SymbolicExpressionTreeManipulator.cs

    r3239 r3294  
    3131  /// A base class for operators that manipulate real-valued vectors.
    3232  /// </summary>
    33   [Item("RealVectorManipulator", "A base class for operators that manipulate real-valued vectors.")]
     33  [Item("SymbolicExpressionTreeManipulator", "A base class for operators that manipulate symbolic expression trees.")]
    3434  [StorableClass]
    35   public abstract class RealVectorManipulator : SingleSuccessorOperator, IRealVectorManipulator, IStochasticOperator, ISymbolicExpressionTreeOperator {
    36     public override bool CanChangeName {
    37       get { return false; }
     35  public abstract class SymbolicExpressionTreeManipulator : SymbolicExpressionTreeOperator, IManipulator {
     36    private const string FailedManipulationEventsParameterName = "FailedManipulationEvents";
     37
     38    #region Parameter Properties
     39    public IValueParameter<IntValue> FailedManipulationEventsParameter {
     40      get { return (IValueParameter<IntValue>)Parameters[FailedManipulationEventsParameterName]; }
    3841    }
     42    #endregion
    3943
    40     public ILookupParameter<IRandom> RandomParameter {
    41       get { return (LookupParameter<IRandom>)Parameters["Random"]; }
     44    #region Properties
     45    public IntValue FailedManipulationEvents {
     46      get { return FailedManipulationEventsParameter.Value; }
    4247    }
    43     public ILookupParameter<RealVector> RealVectorParameter {
    44       get { return (ILookupParameter<RealVector>)Parameters["RealVector"]; }
    45     }
    46     public IValueLookupParameter<DoubleMatrix> BoundsParameter {
    47       get { return (IValueLookupParameter<DoubleMatrix>)Parameters["Bounds"]; }
    48     }
     48    #endregion
    4949
    50     protected RealVectorManipulator()
     50    public SymbolicExpressionTreeManipulator()
    5151      : base() {
    52       Parameters.Add(new LookupParameter<IRandom>("Random", "The pseudo random number generator which should be used for stochastic manipulation operators."));
    53       Parameters.Add(new LookupParameter<RealVector>("RealVector", "The vector which should be manipulated."));
    54       Parameters.Add(new ValueLookupParameter<DoubleMatrix>("Bounds", "The lower and upper bounds of the real vector."));
     52      Parameters.Add(new ValueParameter<IntValue>(FailedManipulationEventsParameterName, "The number of failed manipulation events.", new IntValue()));
    5553    }
    5654
    5755    public sealed override IOperation Apply() {
    58       RealVector vector = RealVectorParameter.ActualValue;
    59       Manipulate(RandomParameter.ActualValue, vector);
    60       DoubleMatrix bounds = BoundsParameter.ActualValue;
    61       if (bounds != null) BoundsChecker.Apply(vector, bounds);
     56      SymbolicExpressionTree tree = SymbolicExpressionTreeParameter.ActualValue;
     57      bool success;
     58      Manipulate(RandomParameter.ActualValue, tree, SymbolicExpressionGrammarParameter.ActualValue,
     59        MaxTreeSizeParameter.ActualValue, MaxTreeHeightParameter.ActualValue, out success);
     60
     61      if (!success) FailedManipulationEvents.Value++;
    6262      return base.Apply();
    6363    }
    6464
    65     protected abstract void Manipulate(IRandom random, RealVector realVector);
     65    protected abstract void Manipulate(IRandom random, SymbolicExpressionTree symbolicExpressionTree, ISymbolicExpressionGrammar grammar,
     66      IntValue maxTreeSize, IntValue maxTreeHeight, out bool success);
    6667  }
    6768}

  • TabularUnified trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/SymbolicExpressionTreeNode.cs

    r3269 r3294  
    2121
    2222using System;
     23using System.Linq;
    2324using System.Collections.Generic;
    2425using System.Text;
    … …  
    2728using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    2829using HeuristicLab.Data;
     30using System.Diagnostics;
    2931
    3032namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
    … …  
    4648    protected SymbolicExpressionTreeNode(SymbolicExpressionTreeNode original) {
    4749      symbol = original.symbol;
    48       this.subTrees = new List<SymbolicExpressionTreeNode>();
     50      subTrees = new List<SymbolicExpressionTreeNode>();
    4951      foreach (var subtree in original.SubTrees) {
    5052        AddSubTree((SymbolicExpressionTreeNode)subtree.Clone());
    5153      }
     54      dynamicSymbols = new Dictionary<string, int>(original.dynamicSymbols);
    5255    }
    5356
    … …  
    7679      return maxHeight + 1;
    7780    }
    78    
     81
     82    [Storable]
     83    private Dictionary<string, int> dynamicSymbols = new Dictionary<string, int>();
     84    public void AddDynamicSymbol(string symbolName) {
     85      Debug.Assert(!dynamicSymbols.ContainsKey(symbolName));
     86      dynamicSymbols[symbolName] = 0;
     87    }
     88
     89    public void AddDynamicSymbol(string symbolName, int nArguments) {
     90      AddDynamicSymbol(symbolName);
     91      SetDynamicSymbolArgumentCount(symbolName, nArguments);
     92    }
     93
     94    public void RemoveDynamicSymbol(string symbolName) {
     95      dynamicSymbols.Remove(symbolName);
     96    }
     97
     98    public IEnumerable<string> DynamicSymbols {
     99      get { return dynamicSymbols.Keys; }
     100    }
     101
     102    public int GetDynamicSymbolArgumentCount(string symbolName) {
     103      return dynamicSymbols[symbolName];
     104    }
     105    public void SetDynamicSymbolArgumentCount(string symbolName, int nArguments) {
     106      Debug.Assert(dynamicSymbols.ContainsKey(symbolName));
     107      dynamicSymbols[symbolName] = nArguments;
     108    }
     109
    79110    public virtual void ResetLocalParameters(IRandom random) { }
    80111    public virtual void ShakeLocalParameters(IRandom random, double shakingFactor) { }

  • TabularUnified trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Symbols/Addition.cs

    r3256 r3294  
    2020#endregion
    2121
     22using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     23using HeuristicLab.Core;
    2224namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.GeneralSymbols {
     25  [StorableClass]
     26  [Item("Addition", "Symbol that represents the + operator.")]
    2327  public sealed class Addition : Symbol {
    2428  }

  • TabularUnified trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Symbols/Division.cs

    r3256 r3294  
    2020#endregion
    2121
     22using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     23using HeuristicLab.Core;
    2224namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.GeneralSymbols {
     25  [StorableClass]
     26  [Item("Division", "Symbol that represents the / operator.")]
    2327  public sealed class Division : Symbol {
    2428  }

  • TabularUnified trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Symbols/Multiplication.cs

    r3256 r3294  
    2020#endregion
    2121
     22using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     23using HeuristicLab.Core;
    2224namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.GeneralSymbols {
     25  [StorableClass]
     26  [Item("Multiplication", "Symbol that represents the * operator.")]
    2327  public sealed class Multiplication : Symbol {
    2428  }

  • TabularUnified trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Symbols/StartSymbol.cs

    r3256 r3294  
    2020#endregion
    2121
     22using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     23using HeuristicLab.Core;
    2224namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.GeneralSymbols {
     25  [StorableClass]
     26  [Item("StartSymbol", "Special symbol that represents the starting node of the result producing branch of a symbolic expression tree.")]
    2327  public sealed class StartSymbol : Symbol {
     28    public override bool CanChangeName {
     29      get {
     30        return false;
     31      }
     32    }
    2433  }
    2534}

  • TabularUnified trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Symbols/Subtraction.cs

    r3256 r3294  
    2020#endregion
    2121
     22using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     23using HeuristicLab.Core;
    2224namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.GeneralSymbols {
     25  [StorableClass]
     26  [Item("Subtraction", "Symbol that represents the - operator.")]
    2327  public sealed class Subtraction : Symbol {
    2428  }
Note: See TracChangeset for help on using the changeset viewer.