Free cookie consent management tool by TermsFeed Policy Generator

Changeset 3223


Ignore:
Timestamp:
03/26/10 19:34:29 (15 years ago)
Author:
gkronber
Message:

Added work in progress for the artificial ant problem #952 (Artificial Ant Problem for 3.3) and for the symbolic expression tree encoding #937 (Data types and operators for symbolic expression tree encoding).

Location:
trunk/sources
Files:
27 added
2 deleted
6 edited
2 copied
1 moved

Legend:

Unmodified
Added
Removed
  • trunk/sources/HeuristicLab 3.3.sln

    r3219 r3223  
    3939Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab 3.3", "HeuristicLab 3.3\HeuristicLab 3.3.csproj", "{B1DCDECA-B56E-41D5-9850-EF0D3A77DEAF}"
    4040  ProjectSection(ProjectDependencies) = postProject
     41    {125D3006-67F5-48CB-913E-73C0548F17FA} = {125D3006-67F5-48CB-913E-73C0548F17FA}
    4142    {489CFE09-FDF7-4C89-BAB5-BD09CADD61AD} = {489CFE09-FDF7-4C89-BAB5-BD09CADD61AD}
    4243    {72104A0B-90E7-42F3-9ABE-9BBBADD4B943} = {72104A0B-90E7-42F3-9ABE-9BBBADD4B943}
     
    7980    {BF7D9494-A586-457B-8DF9-ED599F9E6A71} = {BF7D9494-A586-457B-8DF9-ED599F9E6A71}
    8081    {DE12659F-87C4-48E6-B2E3-4E73DD95A540} = {DE12659F-87C4-48E6-B2E3-4E73DD95A540}
     82    {F5C0ECAC-EDBA-4024-872A-1F74AFCB20B4} = {F5C0ECAC-EDBA-4024-872A-1F74AFCB20B4}
    8183    {DBECB8B0-B166-4133-BAF1-ED67C3FD7FCA} = {DBECB8B0-B166-4133-BAF1-ED67C3FD7FCA}
    8284    {887425B4-4348-49ED-A457-B7D2C26DDBF9} = {887425B4-4348-49ED-A457-B7D2C26DDBF9}
     
    224226Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Services.Deployment-3.3.Tests", "HeuristicLab.Services.Deployment\3.3\Tests\HeuristicLab.Services.Deployment-3.3.Tests.csproj", "{421D9CCA-5A48-4813-AB9C-ED7025F9CC35}"
    225227EndProject
    226 Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Encodings.SymbolicExpressionTree-3.3", "HeuristicLab.Encodings.SymbolicExpressionTree\3.3\HeuristicLab.Encodings.SymbolicExpressionTree-3.3.csproj", "{125D3006-67F5-48CB-913E-73C0548F17FA}"
     228Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.3", "HeuristicLab.Encodings.SymbolicExpressionTreeEncoding\3.3\HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.3.csproj", "{125D3006-67F5-48CB-913E-73C0548F17FA}"
     229EndProject
     230Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Problems.ArtificialAnt-3.3", "HeuristicLab.Problems.ArtificialAnt\3.3\HeuristicLab.Problems.ArtificialAnt-3.3.csproj", "{F5C0ECAC-EDBA-4024-872A-1F74AFCB20B4}"
    227231EndProject
    228232Global
     
    12591263    {125D3006-67F5-48CB-913E-73C0548F17FA}.Release|x86.ActiveCfg = Release|x86
    12601264    {125D3006-67F5-48CB-913E-73C0548F17FA}.Release|x86.Build.0 = Release|x86
    1261     {125D3006-67F5-48CB-913E-73C0548F17FA}.Services|Any CPU.ActiveCfg = Release|Any CPU
    1262     {125D3006-67F5-48CB-913E-73C0548F17FA}.Services|x64.ActiveCfg = Release|x64
     1265    {125D3006-67F5-48CB-913E-73C0548F17FA}.Services|Any CPU.ActiveCfg = Release|x86
     1266    {125D3006-67F5-48CB-913E-73C0548F17FA}.Services|x64.ActiveCfg = Release|x86
    12631267    {125D3006-67F5-48CB-913E-73C0548F17FA}.Services|x86.ActiveCfg = Release|x86
     1268    {125D3006-67F5-48CB-913E-73C0548F17FA}.Services|x86.Build.0 = Release|x86
     1269    {F5C0ECAC-EDBA-4024-872A-1F74AFCB20B4}.Debug|Any CPU.ActiveCfg = Debug|Any CPU
     1270    {F5C0ECAC-EDBA-4024-872A-1F74AFCB20B4}.Debug|Any CPU.Build.0 = Debug|Any CPU
     1271    {F5C0ECAC-EDBA-4024-872A-1F74AFCB20B4}.Debug|x64.ActiveCfg = Debug|x64
     1272    {F5C0ECAC-EDBA-4024-872A-1F74AFCB20B4}.Debug|x64.Build.0 = Debug|x64
     1273    {F5C0ECAC-EDBA-4024-872A-1F74AFCB20B4}.Debug|x86.ActiveCfg = Debug|x86
     1274    {F5C0ECAC-EDBA-4024-872A-1F74AFCB20B4}.Debug|x86.Build.0 = Debug|x86
     1275    {F5C0ECAC-EDBA-4024-872A-1F74AFCB20B4}.Release|Any CPU.ActiveCfg = Release|Any CPU
     1276    {F5C0ECAC-EDBA-4024-872A-1F74AFCB20B4}.Release|Any CPU.Build.0 = Release|Any CPU
     1277    {F5C0ECAC-EDBA-4024-872A-1F74AFCB20B4}.Release|x64.ActiveCfg = Release|x86
     1278    {F5C0ECAC-EDBA-4024-872A-1F74AFCB20B4}.Release|x64.Build.0 = Release|x86
     1279    {F5C0ECAC-EDBA-4024-872A-1F74AFCB20B4}.Release|x86.ActiveCfg = Release|x86
     1280    {F5C0ECAC-EDBA-4024-872A-1F74AFCB20B4}.Release|x86.Build.0 = Release|x86
     1281    {F5C0ECAC-EDBA-4024-872A-1F74AFCB20B4}.Services|Any CPU.ActiveCfg = Release|Any CPU
     1282    {F5C0ECAC-EDBA-4024-872A-1F74AFCB20B4}.Services|x64.ActiveCfg = Release|x64
     1283    {F5C0ECAC-EDBA-4024-872A-1F74AFCB20B4}.Services|x86.ActiveCfg = Release|x86
    12641284  EndGlobalSection
    12651285  GlobalSection(SolutionProperties) = preSolution
  • trunk/sources/HeuristicLab 3.3/Files.txt

    r3196 r3223  
    2424HeuristicLab.Encodings.PermutationEncoding\3.3:HeuristicLab.Encodings.PermutationEncoding-3.3.dll
    2525HeuristicLab.Encodings.RealVectorEncoding\3.3:HeuristicLab.Encodings.RealVectorEncoding-3.3.dll
     26HeuristicLab.Encodings.SymbolicExpressionTreeEncoding\3.3:HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.3.dll
    2627HeuristicLab.Logging\3.3:HeuristicLab.Logging-3.3.dll
    2728HeuristicLab.MainForm\3.2:HeuristicLab.MainForm-3.2.dll
     
    4041HeuristicLab.Persistence.GUI\3.3:HeuristicLab.Persistence.GUI-3.3.dll
    4142HeuristicLab.PluginAdministrator\3.3:HeuristicLab.PluginAdministrator-3.3.dll
     43HeuristicLab.Problems.ArtificialAnt\3.3:HeuristicLab.Problems.ArtificialAnt-3.3.dll
    4244HeuristicLab.Problems.Knapsack\3.3:HeuristicLab.Problems.Knapsack-3.3.dll
    4345HeuristicLab.Problems.Knapsack.Views\3.3:HeuristicLab.Problems.Knapsack.Views-3.3.dll
  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Creators/ProbabilisticTreeCreator.cs

    r3219 r3223  
    2424using HeuristicLab.Random;
    2525using System;
    26 
    27 namespace HeuristicLab.Encodings.SymbolicExpressionTree {
    28   public class ProbabilisticTreeCreator : OperatorBase {
    29     private static int MAX_TRIES { get { return 100; } }
    30 
    31     public override string Description {
    32       get { return @"Generates a new random operator tree."; }
    33     }
    34 
     26using System.Linq;
     27using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     28using System.Collections.Generic;
     29
     30namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
     31  [StorableClass]
     32  [Item("ProbabilisticTreeCreator", "An operator that creates new symbolic expression trees with uniformly distributed size")]
     33  public class ProbabilisticTreeCreator : SymbolicExpressionTreeCreator {
     34    private const int MAX_TRIES = 100;
    3535    public ProbabilisticTreeCreator()
    3636      : base() {
    37       AddVariableInfo(new VariableInfo("Random", "Uniform random number generator", typeof(MersenneTwister), VariableKind.In));
    38       AddVariableInfo(new VariableInfo("FunctionLibrary", "The function library containing all available functions", typeof(FunctionLibrary), VariableKind.In));
    39       AddVariableInfo(new VariableInfo("MinTreeSize", "The minimal allowed size of the tree", typeof(IntData), VariableKind.In));
    40       AddVariableInfo(new VariableInfo("MaxTreeSize", "The maximal allowed size of the tree", typeof(IntData), VariableKind.In));
    41       AddVariableInfo(new VariableInfo("MaxTreeHeight", "The maximal allowed height of the tree", typeof(IntData), VariableKind.In));
    42       AddVariableInfo(new VariableInfo("FunctionTree", "The created tree", typeof(IGeneticProgrammingModel), VariableKind.New | VariableKind.Out));
    43     }
    44 
    45     public override IOperation Apply(IScope scope) {
    46       IRandom random = GetVariableValue<IRandom>("Random", scope, true);
    47       FunctionLibrary funLibrary = GetVariableValue<FunctionLibrary>("FunctionLibrary", scope, true);
    48       int minTreeSize = GetVariableValue<IntData>("MinTreeSize", scope, true).Data;
    49       int maxTreeSize = GetVariableValue<IntData>("MaxTreeSize", scope, true).Data;
    50       int maxTreeHeight = GetVariableValue<IntData>("MaxTreeHeight", scope, true).Data;
    51 
    52       IFunctionTree root = Create(random, funLibrary, minTreeSize, maxTreeSize, maxTreeHeight);
    53       scope.AddVariable(new HeuristicLab.Core.Variable(scope.TranslateName("FunctionTree"), new GeneticProgrammingModel(root)));
    54       return Util.CreateInitializationOperation(TreeGardener.GetAllSubTrees(root), scope);
    55     }
    56 
    57 
    58     public static IFunctionTree Create(IRandom random, FunctionLibrary funLib, int minSize, int maxSize, int maxHeight) {
    59       int treeSize = random.Next(minSize, maxSize);
    60       IFunctionTree root = null;
     37    }
     38
     39    protected override SymbolicExpressionTree Create(IRandom random, ISymbolicExpressionGrammar grammar, IntValue maxTreeSize, IntValue maxTreeHeight) {
     40      return Apply(random, grammar, maxTreeSize.Value, maxTreeHeight.Value);
     41    }
     42
     43    public SymbolicExpressionTree Apply(IRandom random, ISymbolicExpressionGrammar grammar, int maxTreeSize, int maxTreeHeight) {
     44      // tree size is limited by the grammar and by the explicit size constraints
     45      int allowedMinSize = grammar.MinimalExpressionLength(grammar.StartSymbol);
     46      int allowedMaxSize = Math.Min(maxTreeSize, grammar.MaximalExpressionLength(grammar.StartSymbol));
     47      // select a target tree size uniformly in the possible range (as determined by explicit limits and limits of the grammar)
     48      int treeSize = random.Next(allowedMinSize, allowedMaxSize);
     49      SymbolicExpressionTree tree = new SymbolicExpressionTree();
    6150      int tries = 0;
    62       TreeGardener gardener = new TreeGardener(random, funLib);
    6351      do {
    6452        try {
    65           root = gardener.PTC2(treeSize, maxHeight);
     53          // determine possible root symbols to create a tree of the target size
     54          var possibleRootSymbols = from symbol in grammar.AllowedSymbols(grammar.StartSymbol, 0)
     55                                    where treeSize <= grammar.MaximalExpressionLength(symbol)
     56                                    where treeSize >= grammar.MinimalExpressionLength(symbol)
     57                                    select symbol;
     58          Symbol rootSymbol = SelectRandomSymbol(random, possibleRootSymbols);
     59          tree.Root = PTC2(random, grammar, rootSymbol, treeSize, maxTreeHeight);
    6660        }
    6761        catch (ArgumentException) {
    6862          // try a different size
    69           treeSize = random.Next(minSize, maxSize);
     63          treeSize = random.Next(allowedMinSize, allowedMaxSize);
    7064          tries = 0;
    7165        }
    7266        if (tries++ >= MAX_TRIES) {
    7367          // try a different size
    74           treeSize = random.Next(minSize, maxSize);
     68          treeSize = random.Next(allowedMinSize, allowedMaxSize);
    7569          tries = 0;
    7670        }
    77       } while (root == null || root.GetSize() > maxSize || root.GetHeight() > maxHeight);
     71      } while (tree.Root == null || tree.Size > maxTreeSize || tree.Height > maxTreeHeight);
     72      return tree;
     73    }
     74
     75    private Symbol SelectRandomSymbol(IRandom random, IEnumerable<Symbol> symbols) {
     76      var symbolList = symbols.ToList();
     77      return symbolList[random.Next(symbolList.Count)];
     78    }
     79
     80
     81    private SymbolicExpressionTreeNode PTC2(IRandom random, ISymbolicExpressionGrammar grammar, Symbol rootSymbol, int size, int maxDepth) {
     82      SymbolicExpressionTreeNode root = rootSymbol.CreateTreeNode();
     83      if (size <= 1 || maxDepth <= 1) return root;
     84      List<object[]> list = new List<object[]>();
     85      int currentSize = 1;
     86      int totalListMinSize = grammar.MinimalExpressionLength(rootSymbol) - 1;
     87
     88      int actualArity = SampleArity(random, grammar, rootSymbol, size);
     89      for (int i = 0; i < actualArity; i++) {
     90        // insert a dummy sub-tree and add the pending extension to the list
     91        root.AddSubTree(null);
     92        list.Add(new object[] { root, i, 2 });
     93      }
     94
     95      // while there are pending extension points and we have not reached the limit of adding new extension points
     96      while (list.Count > 0 && totalListMinSize + currentSize < size) {
     97        int randomIndex = random.Next(list.Count);
     98        object[] nextExtension = list[randomIndex];
     99        list.RemoveAt(randomIndex);
     100        SymbolicExpressionTreeNode parent = (SymbolicExpressionTreeNode)nextExtension[0];
     101        int argumentIndex = (int)nextExtension[1];
     102        int extensionDepth = (int)nextExtension[2];
     103        if (extensionDepth + grammar.MinimalExpressionDepth(parent.Symbol) >= maxDepth) {
     104          parent.RemoveSubTree(argumentIndex);
     105          SymbolicExpressionTreeNode branch = CreateMinimalTree(random, grammar, grammar.AllowedSymbols(parent.Symbol, argumentIndex));
     106          parent.InsertSubTree(argumentIndex, branch); // insert a smallest possible tree
     107          currentSize += branch.GetSize();
     108          totalListMinSize -= branch.GetSize();
     109        } else {
     110          var allowedSubFunctions = from s in grammar.AllowedSymbols(parent.Symbol, argumentIndex)
     111                                    where grammar.MinimalExpressionDepth(parent.Symbol) + extensionDepth - 1 < maxDepth
     112                                    where grammar.MaximalExpressionLength(s) > size - totalListMinSize - currentSize ||
     113                                          totalListMinSize + currentSize >= size * 0.9 // if the necessary size is almost reached then also allow
     114                                    // terminals or terminal-branches
     115                                    select s;
     116          Symbol selectedSymbol = SelectRandomSymbol(random, allowedSubFunctions);
     117          SymbolicExpressionTreeNode newTree = selectedSymbol.CreateTreeNode();
     118          parent.RemoveSubTree(argumentIndex);
     119          parent.InsertSubTree(argumentIndex, newTree);
     120          currentSize++;
     121          totalListMinSize--;
     122
     123          actualArity = SampleArity(random, grammar, selectedSymbol, size - currentSize);
     124          for (int i = 0; i < actualArity; i++) {
     125            // insert a dummy sub-tree and add the pending extension to the list
     126            newTree.AddSubTree(null);
     127            list.Add(new object[] { newTree, i, extensionDepth + 1 });
     128          }
     129          totalListMinSize += grammar.MinimalExpressionLength(selectedSymbol);
     130        }
     131      }
     132      // fill all pending extension points
     133      while (list.Count > 0) {
     134        int randomIndex = random.Next(list.Count);
     135        object[] nextExtension = list[randomIndex];
     136        list.RemoveAt(randomIndex);
     137        SymbolicExpressionTreeNode parent = (SymbolicExpressionTreeNode)nextExtension[0];
     138        int a = (int)nextExtension[1];
     139        int d = (int)nextExtension[2];
     140        parent.RemoveSubTree(a);
     141        parent.InsertSubTree(a,
     142          CreateMinimalTree(random, grammar, grammar.AllowedSymbols(parent.Symbol, a))); // append a tree with minimal possible height
     143      }
    78144      return root;
    79145    }
     146
     147    private int SampleArity(IRandom random, ISymbolicExpressionGrammar grammar, Symbol symbol, int targetSize) {
     148      // select actualArity randomly with the constraint that the sub-trees in the minimal arity can become large enough
     149      int minArity = grammar.MinSubTrees(symbol);
     150      int maxArity = grammar.MaxSubTrees(symbol);
     151      if (maxArity >= targetSize) {
     152        maxArity = targetSize;
     153      }
     154      // the min number of sub-trees has to be set to a value that is large enough so that the largest possible tree is at least tree size
     155      // if 1..3 trees are possible and the largest possible first sub-tree is smaller larger than the target size then minArity should be at least 2
     156      int aggregatedLongestExpressionLength = 1;
     157      for (int i = 0; i < maxArity; i++) {
     158        aggregatedLongestExpressionLength += (from s in grammar.AllowedSymbols(symbol, i)
     159                                              select grammar.MaximalExpressionLength(symbol)).Max();
     160        if (aggregatedLongestExpressionLength < targetSize) minArity = i;
     161        else break;
     162      }
     163
     164      // the max number of sub-trees has to be set to a value that is small enough so that the smallest possible tree is at most tree size
     165      // if 1..3 trees are possible and the smallest possible first sub-tree is already larger than the target size then maxArity should be at most 0
     166      int aggregatedShortestExpressionLength = 1;
     167      for (int i = 0; i < maxArity; i++) {
     168        aggregatedShortestExpressionLength += (from s in grammar.AllowedSymbols(symbol, i)
     169                                               select grammar.MinimalExpressionLength(symbol)).Min();
     170        if (aggregatedShortestExpressionLength > targetSize) {
     171          maxArity = i;
     172          break;
     173        }
     174      }
     175      if (minArity > maxArity) throw new ArgumentException();
     176      return random.Next(minArity, maxArity + 1);
     177    }
     178
     179    private SymbolicExpressionTreeNode CreateMinimalTree(IRandom random, ISymbolicExpressionGrammar grammar, IEnumerable<Symbol> symbols) {
     180      // determine possible symbols that will lead to the smallest possible tree
     181      var possibleSymbols = (from s in symbols
     182                             group s by grammar.MinimalExpressionLength(s) into g
     183                             orderby g.Key
     184                             select g).First();
     185      var selectedSymbol = SelectRandomSymbol(random, possibleSymbols);
     186      // build minimal tree by recursive application
     187      var tree = selectedSymbol.CreateTreeNode();
     188      for (int i = 0; i < grammar.MinSubTrees(selectedSymbol); i++)
     189        tree.AddSubTree(CreateMinimalTree(random, grammar, grammar.AllowedSymbols(selectedSymbol, i)));
     190      return tree;
     191    }
     192
     193    //private bool IsRecursiveExpansionPossible(Symbol symbol) {
     194    //  return FindCycle(function, new Stack<IFunction>());
     195    //}
     196
     197    //private Dictionary<IFunction, bool> inCycle = new Dictionary<IFunction, bool>();
     198    //private bool FindCycle(IFunction function, Stack<IFunction> functionChain) {
     199    //  if (inCycle.ContainsKey(function)) {
     200    //    return inCycle[function];
     201    //  } else if (IsTerminal(function)) {
     202    //    inCycle[function] = false;
     203    //    return false;
     204    //  } else if (functionChain.Contains(function)) {
     205    //    inCycle[function] = true;
     206    //    return true;
     207    //  } else {
     208    //    functionChain.Push(function);
     209    //    bool result = false;
     210    //    // all slot indexes
     211    //    for (int i = 0; i < function.MaxSubTrees; i++) {
     212    //      foreach (IFunction subFunction in GetAllowedSubFunctions(function, i)) {
     213    //        result |= FindCycle(subFunction, functionChain);
     214    //      }
     215    //    }
     216
     217    //    functionChain.Pop();
     218    //    inCycle[function] = result;
     219    //    return result;
     220    //  }
     221    //}
     222
    80223  }
    81224}
  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/HeuristicLabEncodingsSymbolicExpressionTreeEncodingPlugin.cs.frame

    r3222 r3223  
    2525using HeuristicLab.PluginInfrastructure;
    2626
    27 namespace HeuristicLab.Encodings.SymbolicExpressionTree {
    28   [Plugin("HeuristicLab.Encodings.SymbolicExpressionTree", "3.3.0.$WCREV$")]
    29   [PluginFile("HeuristicLab.Encodings.SymbolicExpressionTree-3.3.dll", PluginFileType.Assembly)]
     27namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
     28  [Plugin("HeuristicLab.Encodings.SymbolicExpressionTreeEncoding", "3.3.0.$WCREV$")]
     29  [PluginFile("HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.3.dll", PluginFileType.Assembly)]
    3030  [PluginDependency("HeuristicLab.Core", "3.3.0.0")]
    3131  [PluginDependency("HeuristicLab.Data", "3.3.0.0")]
     
    3434  [PluginDependency("HeuristicLab.Persistence", "3.3.0.0")]
    3535  [PluginDependency("HeuristicLab.Random", "3.3.0.0")]
    36   public class HeuristicLabEncodingsSymbolicExpressionTreePlugin : PluginBase {
     36  public class HeuristicLabEncodingsSymbolicExpressionTreeEncodingPlugin : PluginBase {
    3737  }
    3838}
  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Properties/AssemblyInfo.frame

    r3219 r3223  
    2727// set of attributes. Change these attribute values to modify the information
    2828// associated with an assembly.
    29 [assembly: AssemblyTitle("HeuristicLab.Encodings.SymbolicExpressionTree")]
     29[assembly: AssemblyTitle("HeuristicLab.Encodings.SymbolicExpressionTreeEncoding")]
    3030[assembly: AssemblyDescription("HeuristicLab symbolic expression tree encoding and related operators")]
    3131[assembly: AssemblyConfiguration("")]
  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Symbol.cs

    r3219 r3223  
    2525using HeuristicLab.Core;
    2626using System.Linq;
    27 
    28 namespace HeuristicLab.Encodings.SymbolicExpressionTree {
    29   public abstract class Symbol {
     27using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     28
     29namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
     30  [StorableClass]
     31  [Item("Symbol", "Represents a symbol in a symbolic function tree.")]
     32  public abstract class Symbol : Item {
    3033    private List<List<Symbol>> allowedSubFunctions = new List<List<Symbol>>();
    3134    private int minArity = -1;
     
    4447        if (value != name) {
    4548          name = value;
    46           FireChanged();
    47         }
    48       }
    49     }
    50 
    51     protected Function() {
     49        }
     50      }
     51    }
     52
     53    protected Symbol() {
    5254      name = this.GetType().Name;
    53     }
    54 
    55     public virtual string Description {
    56       get { return "Description for this function is missing (TODO)"; }
    5755    }
    5856
     
    6563        if (minArity != value) {
    6664          minArity = value;
    67           while (minArity > allowedSubFunctions.Count) allowedSubFunctions.Add(new List<IFunction>());
     65          while (minArity > allowedSubFunctions.Count) allowedSubFunctions.Add(new List<Symbol>());
    6866          ResetCachedValues();
    69           FireChanged();
    7067        }
    7168      }
     
    9289          }
    9390          ResetCachedValues();
    94           FireChanged();
    9591        }
    9692      }
     
    10298        if (minTreeSize <= 0) {
    10399          RecalculateMinimalTreeSize();
    104           FireChanged();
    105100        }
    106101        // Debug.Assert(minTreeSize > 0);
     
    113108        if (minTreeHeight <= 0) {
    114109          RecalculateMinimalTreeHeight();
    115           FireChanged();
    116110        }
    117111        // Debug.Assert(minTreeHeight > 0);
     
    126120        if (value != tickets) {
    127121          tickets = value;
    128           FireChanged();
    129122        }
    130123      }
     
    136129        if (initializer != value) {
    137130          initializer = value;
    138           FireChanged();
    139131        }
    140132      }
     
    146138        if (manipulator != value) {
    147139          manipulator = value;
    148           FireChanged();
    149         }
    150       }
    151     }
    152 
    153     public virtual IFunctionTree GetTreeNode() {
    154       return new FunctionTree(this);
    155     }
    156 
    157     public ICollection<IFunction> GetAllowedSubFunctions(int index) {
     140        }
     141      }
     142    }
     143
     144    public virtual SymbolicExpressionTreeNode CreateTreeNode() {
     145      return new SymbolicExpressionTreeNode(this);
     146    }
     147
     148    public IEnumerable<Symbol> GetAllowedSubFunctions(int index) {
    158149      if (index < 0 || index > MaxSubTrees) throw new ArgumentException("Index outside of allowed range. index = " + index);
    159150      return allowedSubFunctions[index];
    160151    }
    161152
    162     public void AddAllowedSubFunction(IFunction function, int index) {
     153    public void AddAllowedSubFunction(Symbol symbol, int index) {
    163154      if (index < 0 || index > MaxSubTrees) throw new ArgumentException("Index outside of allowed range. index = " + index);
    164155      if (allowedSubFunctions[index] == null) {
    165         allowedSubFunctions[index] = new List<IFunction>();
    166       }
    167       if (!allowedSubFunctions[index].Contains(function)) {
    168         allowedSubFunctions[index].Add(function);
     156        allowedSubFunctions[index] = new List<Symbol>();
     157      }
     158      if (!allowedSubFunctions[index].Contains(symbol)) {
     159        allowedSubFunctions[index].Add(symbol);
    169160      }
    170161      ResetCachedValues();
    171       FireChanged();
    172     }
    173     public void RemoveAllowedSubFunction(IFunction function, int index) {
     162    }
     163    public void RemoveAllowedSubFunction(Symbol symbol, int index) {
    174164      if (index < 0 || index > MaxSubTrees) throw new ArgumentException("Index outside of allowed range. index = " + index);
    175       if (allowedSubFunctions[index].Contains(function)) {
    176         allowedSubFunctions[index].Remove(function);
     165      if (allowedSubFunctions[index].Contains(symbol)) {
     166        allowedSubFunctions[index].Remove(symbol);
    177167        ResetCachedValues();
    178         FireChanged();
    179168      }
    180169    }
     
    185174    }
    186175
    187     public bool IsAllowedSubFunction(IFunction function, int index) {
    188       return GetAllowedSubFunctions(index).Contains(function);
     176    public bool IsAllowedSubFunction(Symbol symbol, int index) {
     177      return GetAllowedSubFunctions(index).Contains(symbol);
    189178    }
    190179
     
    213202    }
    214203
    215     public override IView CreateView() {
    216       return new FunctionView(this);
    217     }
    218 
    219204    public override string ToString() {
    220205      return name;
    221206    }
    222 
    223     #region persistence
    224     public override object Clone(IDictionary<Guid, object> clonedObjects) {
    225       Function clone = (Function)base.Clone(clonedObjects);
    226       if (initializer != null) clone.initializer = (IOperator)Auxiliary.Clone(initializer, clonedObjects);
    227       else clone.initializer = null;
    228       if (manipulator != null) clone.manipulator = (IOperator)Auxiliary.Clone(manipulator, clonedObjects);
    229       else clone.manipulator = null;
    230       clone.MaxSubTrees = maxArity;
    231       clone.MinSubTrees = minArity;
    232       clone.Tickets = tickets;
    233       clone.allowedSubFunctions.Clear();
    234       for (int i = 0; i < MaxSubTrees; i++) {
    235         var allowedSubFunctionsForSlot = new List<IFunction>();
    236         foreach (IFunction f in GetAllowedSubFunctions(i)) {
    237           allowedSubFunctionsForSlot.Add((IFunction)Auxiliary.Clone(f, clonedObjects));
    238         }
    239         clone.allowedSubFunctions.Add(allowedSubFunctionsForSlot);
    240       }
    241       return clone;
    242     }
    243 
    244     public override XmlNode GetXmlNode(string name, XmlDocument document, IDictionary<Guid, IStorable> persistedObjects) {
    245       XmlNode node = base.GetXmlNode(name, document, persistedObjects);
    246       XmlAttribute minSubTreesAttr = document.CreateAttribute("MinSubTrees");
    247       minSubTreesAttr.Value = XmlConvert.ToString(MinSubTrees);
    248       XmlAttribute maxSubTreesAttr = document.CreateAttribute("MaxSubTrees");
    249       maxSubTreesAttr.Value = XmlConvert.ToString(MaxSubTrees);
    250       node.Attributes.Append(minSubTreesAttr);
    251       node.Attributes.Append(maxSubTreesAttr);
    252       if (initializer != null)
    253         node.AppendChild(PersistenceManager.Persist("Initializer", initializer, document, persistedObjects));
    254       if (manipulator != null)
    255         node.AppendChild(PersistenceManager.Persist("Manipulator", manipulator, document, persistedObjects));
    256       for (int i = 0; i < MaxSubTrees; i++) {
    257         XmlNode slotNode = document.CreateElement("AllowedSubFunctions");
    258         XmlAttribute slotAttr = document.CreateAttribute("Slot");
    259         slotAttr.Value = XmlConvert.ToString(i);
    260         slotNode.Attributes.Append(slotAttr);
    261         node.AppendChild(slotNode);
    262         foreach (IFunction f in GetAllowedSubFunctions(i)) {
    263           slotNode.AppendChild(PersistenceManager.Persist(f, document, persistedObjects));
    264         }
    265       }
    266       return node;
    267     }
    268 
    269     public override void Populate(XmlNode node, IDictionary<Guid, IStorable> restoredObjects) {
    270       base.Populate(node, restoredObjects);
    271       MinSubTrees = XmlConvert.ToInt32(node.Attributes["MinSubTrees"].Value);
    272       MaxSubTrees = XmlConvert.ToInt32(node.Attributes["MaxSubTrees"].Value);
    273       if (node.SelectSingleNode("Initializer") != null) {
    274         initializer = (IOperator)PersistenceManager.Restore(node.SelectSingleNode("Initializer"), restoredObjects);
    275       }
    276       if (node.SelectSingleNode("Manipulator") != null) {
    277         manipulator = (IOperator)PersistenceManager.Restore(node.SelectSingleNode("Manipulator"), restoredObjects);
    278       }
    279       foreach (var subFunctionsList in allowedSubFunctions) subFunctionsList.Clear();
    280       foreach (XmlNode allowedSubFunctionsNode in node.SelectNodes("AllowedSubFunctions")) {
    281         int slot = XmlConvert.ToInt32(allowedSubFunctionsNode.Attributes["Slot"].Value);
    282         foreach (XmlNode fNode in allowedSubFunctionsNode.ChildNodes) {
    283           AddAllowedSubFunction((IFunction)PersistenceManager.Restore(fNode, restoredObjects), slot);
    284         }
    285       }
    286     }
    287     #endregion
    288207  }
    289208}
  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/SymbolicExpressionGrammar.cs

    r3222 r3223  
    11#region License Information
    22/* HeuristicLab
    3  * Copyright (C) 2002-2008 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
     3 * Copyright (C) 2002-2010 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
    44 *
    55 * This file is part of HeuristicLab.
     
    2626using HeuristicLab.Core;
    2727using System.Xml;
    28 using HeuristicLab.GP.Interfaces;
     28using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    2929
    30 namespace HeuristicLab.GP {
    31   public class FunctionLibrary : ItemBase, IEditable {
    32     private List<IFunction> functions = new List<IFunction>();
    33     public IEnumerable<IFunction> Functions {
    34       get { return functions; }
     30namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
     31  [StorableClass]
     32  [Item("SymbolicExpressionGrammar", "Represents a grammar that defines the syntax of symbolic expression trees.")]
     33  public class SymbolicExpressionGrammar : Item, ISymbolicExpressionGrammar {
     34    //private List<Symbol> symbols = new List<Symbol>();
     35    //public IEnumerable<Symbol> Symbols {
     36    //  get { return symbols; }
     37    //}
     38
     39    // internal implementation of a symbol for the start symbol
     40    private class EmptySymbol : Symbol {
    3541    }
    3642
    37     public FunctionLibrary()
     43    private Dictionary<Symbol, Dictionary<int, IEnumerable<Symbol>>> allowedSymbols;
     44
     45    public SymbolicExpressionGrammar()
    3846      : base() {
     47      startSymbol = new EmptySymbol();
     48      allowedSymbols = new Dictionary<Symbol, Dictionary<int, IEnumerable<Symbol>>>();
    3949    }
    4050
    41     public void AddFunction(IFunction fun) {
    42       if (!functions.Contains(fun)) {
    43         functions.Add(fun);
    44         fun.Changed += new EventHandler(fun_Changed);
    45         OnChanged();
    46       }
     51    //public void AddSymbol(Symbol symbol) {
     52    //  if (!symbols.Contains(symbol)) {
     53    //    symbols.Add(symbol);
     54    //    symbol.ToStringChanged += new EventHandler(symbol_ToStringChanged);
     55
     56    //    OnToStringChanged();
     57    //  }
     58    //}
     59
     60    //public void RemoveSymbol(Symbol symbol) {
     61    //  symbols.Remove(symbol);
     62    //  symbol.ToStringChanged -= new EventHandler(symbol_ToStringChanged);
     63
     64    //  // remove the operator from the allowed sub-functions of all functions
     65    //  foreach (Symbol f in Symbols) {
     66    //    for (int i = 0; i < f.MaxSubTrees; i++) {
     67    //      f.RemoveAllowedSubFunction(symbol, i);
     68    //    }
     69    //  }
     70    //  OnToStringChanged();
     71    //}
     72
     73    private void symbol_ToStringChanged(object sender, EventArgs e) {
     74      OnToStringChanged();
    4775    }
    4876
    49     public void RemoveFunction(IFunction fun) {
    50       functions.Remove(fun);
    51       fun.Changed -= new EventHandler(fun_Changed);
     77    #region ISymbolicExpressionGrammar Members
    5278
    53       // remove the operator from the allowed sub-functions of all functions
    54       foreach (IFunction f in Functions) {
    55         for (int i = 0; i < f.MaxSubTrees; i++) {
    56           f.RemoveAllowedSubFunction(fun, i);
    57         }
    58       }
    59       OnChanged();
     79    public Symbol startSymbol;
     80    public Symbol StartSymbol {
     81      get { return startSymbol; }
     82    }
     83   
     84    public IEnumerable<Symbol> AllowedSymbols(Symbol parent, int argumentIndex) {
     85      return allowedSymbols[parent][argumentIndex];
    6086    }
    6187
    62     void fun_Changed(object sender, EventArgs e) {
    63       OnChanged();
     88    public int MinimalExpressionLength(Symbol start) {
     89      throw new NotImplementedException();
    6490    }
    6591
    66     #region persistence
    67     public override XmlNode GetXmlNode(string name, XmlDocument document, IDictionary<Guid, IStorable> persistedObjects) {
    68       XmlNode node = base.GetXmlNode(name, document, persistedObjects);
    69       foreach (IFunction f in functions) {
    70         node.AppendChild(PersistenceManager.Persist("Function", f, document, persistedObjects));
    71       }
    72       return node;
     92    public int MaximalExpressionLength(Symbol start) {
     93      throw new NotImplementedException();
    7394    }
    7495
    75     public override void Populate(XmlNode node, IDictionary<Guid, IStorable> restoredObjects) {
    76       base.Populate(node, restoredObjects);
    77       foreach (XmlNode fNode in node.SelectNodes("Function")) {
    78         AddFunction((IFunction)PersistenceManager.Restore(fNode, restoredObjects));
    79       }
     96    public int MinimalExpressionDepth(Symbol start) {
     97      throw new NotImplementedException();
    8098    }
    8199
    82     public override object Clone(IDictionary<Guid, object> clonedObjects) {
    83       FunctionLibrary clone = (FunctionLibrary)base.Clone(clonedObjects);
    84       foreach (var function in functions) {
    85         clone.AddFunction((Function)Auxiliary.Clone(function, clonedObjects));
    86       }
    87       return clone;
    88     }
    89     #endregion
    90 
    91     public override IView CreateView() {
    92       return new FunctionLibraryEditor(this);
     100    public int MinSubTrees(Symbol start) {
     101      throw new NotImplementedException();
    93102    }
    94103
    95     #region IEditable Members
    96 
    97     public IEditor CreateEditor() {
    98       return new FunctionLibraryEditor(this);
     104    public int MaxSubTrees(Symbol start) {
     105      throw new NotImplementedException();
    99106    }
    100107
  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/SymbolicExpressionTree.cs

    r3219 r3223  
    2525using HeuristicLab.Core;
    2626using System.Xml;
     27using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    2728
    28 namespace HeuristicLab.Encodings.SymbolicExpressionTree {
    29   public class SymbolicExpressionTree  {
    30     private List<SymbolicExpressionTree> subTrees;
    31     private IFunction function;
    32 
    33     public SymbolicExpressionTree() {
    34     }
    35 
    36     public SymbolicExpressionTree(Symbol symbol) {
    37       subTrees = new List<SymbolicExpressionTree>();
    38       this.function = function;
    39     }
    40 
    41     protected SymbolicExpressionTree(SymbolicExpressionTree original) {
    42       this.function = original.Function;
    43       this.subTrees = new List<SymbolicExpressionTree>(original.SubTrees.Count);
    44       foreach (SymbolicExpressionTree originalSubTree in original.SubTrees) {
    45         this.SubTrees.Add((SymbolicExpressionTree)originalSubTree.Clone());
     29namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
     30  [StorableClass]
     31  [Item("SymbolicExpressionTree", "Represents a symbolic expression tree.")]
     32  public class SymbolicExpressionTree : Item {
     33    private SymbolicExpressionTreeNode root;
     34    public SymbolicExpressionTreeNode Root {
     35      get { return root; }
     36      set {
     37        if (value == null) throw new ArgumentNullException();
     38        else if (value != root) {
     39          root = value;
     40          OnToStringChanged();
     41        }
    4642      }
    4743    }
    4844
    49     public virtual bool HasLocalParameters {
    50       get { return false; }
     45    public int Size {
     46      get {
     47        return root.GetSize();
     48      }
    5149    }
    5250
    53     public virtual IList<SymbolicExpressionTree> SubTrees {
    54       get { return subTrees; }
     51    public int Height {
     52      get {
     53        return root.GetHeight();
     54      }
    5555    }
    5656
    57     public Symbol Function {
    58       get { return function; }
    59       protected set { function = value; }
     57    public SymbolicExpressionTree() : base() { }
     58
     59    public SymbolicExpressionTree(SymbolicExpressionTreeNode root) : base() { }
     60
     61    public override IDeepCloneable Clone(Cloner cloner) {
     62      SymbolicExpressionTree clone = new SymbolicExpressionTree();
     63      cloner.RegisterClonedObject(this, clone);
     64      clone.root = (SymbolicExpressionTreeNode)this.root.Clone();
     65      return clone;
    6066    }
    61 
    62     public int GetSize() {
    63       int size = 1;
    64       foreach (SymbolicExpressionTree tree in SubTrees) size += tree.GetSize();
    65       return size;
    66     }
    67 
    68     public int GetHeight() {
    69       int maxHeight = 0;
    70       foreach (SymbolicExpressionTree tree in SubTrees) maxHeight = Math.Max(maxHeight, tree.GetHeight());
    71       return maxHeight + 1;
    72     }
    73 
    74     public virtual IOperation CreateShakingOperation(IScope scope) {
    75       return null;
    76     }
    77 
    78     public virtual IOperation CreateInitOperation(IScope scope) {
    79       return null;
    80     }
    81 
    82     public void AddSubTree(SymbolicExpressionTree tree) {
    83       SubTrees.Add(tree);
    84     }
    85 
    86     public virtual void InsertSubTree(int index, SymbolicExpressionTree tree) {
    87       SubTrees.Insert(index, tree);
    88     }
    89 
    90     public virtual void RemoveSubTree(int index) {
    91       SubTrees.RemoveAt(index);
    92     }
    93 
    94     public override string ToString() {
    95       return Function.Name;
    96     }
    97 
    98 
    99     #region IStorable Members
    100 
    101     public Guid Guid {
    102       get { throw new NotSupportedException(); }
    103     }
    104 
    105     public virtual object Clone() {
    106       return new SymbolicExpressionTree(this);
    107     }
    108 
    109     public object Clone(IDictionary<Guid, object> clonedObjects) {
    110       throw new NotImplementedException();
    111     }
    112 
    113     public virtual XmlNode GetXmlNode(string name, XmlDocument document, IDictionary<Guid, IStorable> persistedObjects) {
    114       return null;
    115     }
    116 
    117     public virtual void Populate(XmlNode node, IDictionary<Guid, IStorable> restoredObjects) {
    118     }
    119 
    120     #endregion
    12167  }
    12268}
Note: See TracChangeset for help on using the changeset viewer.