Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
07/06/10 11:59:50 (14 years ago)
Author:
gkronber
Message:

Minor improvements concerning efficiency of symbolic expression tree encoding data structures and operators. #1073

Location:
trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3
Files:
1 added
4 edited

Legend:

Unmodified
Added
Removed
  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Crossovers/SubtreeCrossover.cs

    r3989 r3997  
    6767      int maxInsertedBranchHeight = maxTreeHeight - GetBranchLevel(parent0.Root, crossoverPoint0);
    6868
    69       var allowedBranches = (from branch in parent1.Root.IterateNodesPostfix()
    70                              where branch.GetSize() < maxInsertedBranchSize
    71                              where branch.GetHeight() < maxInsertedBranchHeight
    72                              where IsMatchingPointType(crossoverPoint0, replacedSubtreeIndex, branch)
    73                              select branch).ToList();
     69      List<SymbolicExpressionTreeNode> allowedBranches = new List<SymbolicExpressionTreeNode>();
     70      parent1.Root.ForEachNodePostfix((n) => {
     71        if (n.GetSize() < maxInsertedBranchSize &&
     72          n.GetHeight() < maxInsertedBranchHeight &&
     73          IsMatchingPointType(crossoverPoint0, replacedSubtreeIndex, n))
     74          allowedBranches.Add(n);
     75      });
    7476
    75       if (allowedBranches.Count() == 0) {
     77      if (allowedBranches.Count == 0) {
    7678        success = false;
    7779        return parent0;
     
    8991
    9092    private static bool IsMatchingPointType(SymbolicExpressionTreeNode parent, int replacedSubtreeIndex, SymbolicExpressionTreeNode branch) {
    91       // check point type for the whole branch
    92       foreach (var node in branch.IterateNodesPostfix()) {
    93         if (!parent.Grammar.ContainsSymbol(node.Symbol)) return false;
    94         else if (node.SubTrees.Count < parent.Grammar.GetMinSubtreeCount(node.Symbol)) return false;
    95         else if (node.SubTrees.Count > parent.Grammar.GetMaxSubtreeCount(node.Symbol)) return false;
    96       }
    97 
    9893      // check syntax constraints of direct parent - child relation
    9994      if (!parent.Grammar.IsAllowedChild(parent.Symbol, branch.Symbol, replacedSubtreeIndex)) return false;
    10095
    101       return true;
     96      bool result = true;
     97      // check point type for the whole branch
     98      branch.ForEachNodePostfix((n) => {
     99        result &= n.SubTrees.Count >= parent.Grammar.GetMinSubtreeCount(n.Symbol);
     100        result &= n.SubTrees.Count <= parent.Grammar.GetMaxSubtreeCount(n.Symbol);
     101        result &= parent.Grammar.ContainsSymbol(n.Symbol);
     102      });
     103      return result;
    102104    }
    103105
    104106    private static void SelectCrossoverPoint(IRandom random, SymbolicExpressionTree parent0, double internalNodeProbability, int maxBranchSize, int maxBranchHeight, out SymbolicExpressionTreeNode crossoverPoint, out int subtreeIndex) {
    105       var crossoverPoints = (from branch in parent0.Root.IterateNodesPostfix()
    106                              where branch.SubTrees.Count > 0
    107                              where branch != parent0.Root
    108                              where branch.GetSize() < maxBranchSize
    109                              where branch.GetHeight() < maxBranchHeight
    110                              from index in Enumerable.Range(0, branch.SubTrees.Count)
    111                              let p = new { CrossoverPoint = branch, SubtreeIndex = index, IsLeaf = branch.SubTrees[index].SubTrees.Count == 0 }
    112                              select p).ToList();
    113       var internalCrossoverPoints = (from p in crossoverPoints
    114                                      where !p.IsLeaf
    115                                      select p).ToList();
    116       var leafCrossoverPoints = (from p in crossoverPoints
    117                                  where p.IsLeaf
    118                                  select p).ToList();
    119       if (internalCrossoverPoints.Count == 0) {
     107      if (internalNodeProbability < 0.0 || internalNodeProbability > 1.0) throw new ArgumentException("internalNodeProbability");
     108      List<CrossoverPoint> internalCrossoverPoints = new List<CrossoverPoint>();
     109      List<CrossoverPoint> leafCrossoverPoints = new List<CrossoverPoint>();
     110      parent0.Root.ForEachNodePostfix((n) => {
     111        if (n.SubTrees.Count > 0 &&
     112          n.GetSize() < maxBranchSize &&
     113          n.GetHeight() < maxBranchHeight &&
     114          n != parent0.Root
     115          ) {
     116          foreach (var child in n.SubTrees) {
     117            if (child.SubTrees.Count > 0)
     118              internalCrossoverPoints.Add(new CrossoverPoint(n, child));
     119            else
     120              leafCrossoverPoints.Add(new CrossoverPoint(n, child));
     121          }
     122        }
     123      });
     124      if (random.NextDouble() < internalNodeProbability) {
     125        // select from internal node if possible
     126        if (internalCrossoverPoints.Count > 0) {
     127          // select internal crossover point or leaf
     128          var selectedCrossoverPoint = internalCrossoverPoints[random.Next(internalCrossoverPoints.Count)];
     129          crossoverPoint = selectedCrossoverPoint.Parent;
     130          subtreeIndex = selectedCrossoverPoint.SubtreeIndex;
     131        } else {
     132          // otherwise select external node
     133          var selectedCrossoverPoint = leafCrossoverPoints[random.Next(leafCrossoverPoints.Count)];
     134          crossoverPoint = selectedCrossoverPoint.Parent;
     135          subtreeIndex = selectedCrossoverPoint.SubtreeIndex;
     136        }
     137      } else if (leafCrossoverPoints.Count > 0) {
     138        // select from leaf crossover point if possible
    120139        var selectedCrossoverPoint = leafCrossoverPoints[random.Next(leafCrossoverPoints.Count)];
    121         crossoverPoint = selectedCrossoverPoint.CrossoverPoint;
    122         subtreeIndex = selectedCrossoverPoint.SubtreeIndex;
    123       } else if (leafCrossoverPoints.Count == 0) {
    124         var selectedCrossoverPoint = internalCrossoverPoints[random.Next(internalCrossoverPoints.Count)];
    125         crossoverPoint = selectedCrossoverPoint.CrossoverPoint;
    126         subtreeIndex = selectedCrossoverPoint.SubtreeIndex;
    127       } else if (random.NextDouble() < internalNodeProbability && internalCrossoverPoints.Count > 0) {
    128         // select internal crossover point or leaf
    129         var selectedCrossoverPoint = internalCrossoverPoints[random.Next(internalCrossoverPoints.Count)];
    130         crossoverPoint = selectedCrossoverPoint.CrossoverPoint;
     140        crossoverPoint = selectedCrossoverPoint.Parent;
    131141        subtreeIndex = selectedCrossoverPoint.SubtreeIndex;
    132142      } else {
    133         var selectedCrossoverPoint = leafCrossoverPoints[random.Next(leafCrossoverPoints.Count)];
    134         crossoverPoint = selectedCrossoverPoint.CrossoverPoint;
     143        // otherwise select internal crossover point
     144        var selectedCrossoverPoint = internalCrossoverPoints[random.Next(internalCrossoverPoints.Count)];
     145        crossoverPoint = selectedCrossoverPoint.Parent;
    135146        subtreeIndex = selectedCrossoverPoint.SubtreeIndex;
    136147      }
     
    139150    private static SymbolicExpressionTreeNode SelectRandomBranch(IRandom random, IEnumerable<SymbolicExpressionTreeNode> branches, double internalNodeProbability) {
    140151      if (internalNodeProbability < 0.0 || internalNodeProbability > 1.0) throw new ArgumentException("internalNodeProbability");
    141       var allowedInternalBranches = (from branch in branches
     152      List<SymbolicExpressionTreeNode> allowedInternalBranches;
     153      List<SymbolicExpressionTreeNode> allowedLeafBranches;
     154      if (random.NextDouble() < internalNodeProbability) {
     155        // select internal node if possible
     156        allowedInternalBranches = (from branch in branches
     157                                   where branch.SubTrees.Count > 0
     158                                   select branch).ToList();
     159        if (allowedInternalBranches.Count > 0) {
     160          return allowedInternalBranches.SelectRandom(random);
     161        } else {
     162          // no internal nodes allowed => select leaf nodes
     163          allowedLeafBranches = (from branch in branches
     164                                 where branch.SubTrees.Count == 0
     165                                 select branch).ToList();
     166          return allowedLeafBranches.SelectRandom(random);
     167        }
     168      } else {
     169        // select leaf node if possible
     170        allowedLeafBranches = (from branch in branches
     171                               where branch.SubTrees.Count == 0
     172                               select branch).ToList();
     173        if (allowedLeafBranches.Count > 0) {
     174          return allowedLeafBranches.SelectRandom(random);
     175        } else {
     176          allowedInternalBranches = (from branch in branches
    142177                                     where branch.SubTrees.Count > 0
    143178                                     select branch).ToList();
    144       var allowedLeafBranches = (from branch in branches
    145                                  where branch.SubTrees.Count == 0
    146                                  select branch).ToList();
    147       if (allowedInternalBranches.Count == 0) {
    148         return allowedLeafBranches.SelectRandom(random);
    149       } else if (allowedLeafBranches.Count == 0) {
    150         return allowedInternalBranches.SelectRandom(random);
    151       } else if (random.NextDouble() < internalNodeProbability) {
    152         // when leaf and internal nodes are possible then choose either a leaf or internal node with internalNodeProbability
    153         return allowedInternalBranches.SelectRandom(random);
    154       } else {
    155         return allowedLeafBranches.SelectRandom(random);
     179          return allowedInternalBranches.SelectRandom(random);
     180        }
    156181      }
    157182    }
  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/SymbolicExpressionTreeNode.cs

    r3988 r3997  
    4343    private short size;
    4444    private short height;
    45     private List<SymbolicExpressionTreeNode> prefixForm;
    46     private List<SymbolicExpressionTreeNode> postfixForm;
    4745
    4846    public Symbol Symbol {
     
    6462
    6563    public SymbolicExpressionTreeNode(Symbol symbol) {
    66       subTrees = new List<SymbolicExpressionTreeNode>();
     64      subTrees = new List<SymbolicExpressionTreeNode>(3);
    6765      this.symbol = symbol;
    6866    }
     
    137135
    138136    public IEnumerable<SymbolicExpressionTreeNode> IterateNodesPrefix() {
    139       if (prefixForm == null) {
    140         prefixForm = new List<SymbolicExpressionTreeNode>(200);
    141         ForEachNodePrefix(x => prefixForm.Add(x));
    142       }
    143       return prefixForm;
     137      List<SymbolicExpressionTreeNode> list = new List<SymbolicExpressionTreeNode>();
     138      ForEachNodePrefix((n) => list.Add(n));
     139      return list;
    144140    }
    145141
    146     private void ForEachNodePrefix(Action<SymbolicExpressionTreeNode> a) {
     142    public void ForEachNodePrefix(Action<SymbolicExpressionTreeNode> a) {
    147143      a(this);
    148144      for (int i = 0; i < SubTrees.Count; i++) {
     
    152148
    153149    public IEnumerable<SymbolicExpressionTreeNode> IterateNodesPostfix() {
    154       if (postfixForm == null) {
    155         postfixForm = new List<SymbolicExpressionTreeNode>(200);
    156         ForEachNodePostfix(x => postfixForm.Add(x));
    157       }
    158       return postfixForm;
     150      List<SymbolicExpressionTreeNode> list = new List<SymbolicExpressionTreeNode>();
     151      ForEachNodePostfix((n) => list.Add(n));
     152      return list;
    159153    }
    160154
    161     private void ForEachNodePostfix(Action<SymbolicExpressionTreeNode> a) {
     155    public void ForEachNodePostfix(Action<SymbolicExpressionTreeNode> a) {
    162156      for (int i = 0; i < SubTrees.Count; i++) {
    163157        SubTrees[i].ForEachNodePrefix(a);
     
    190184    private void ResetCachedValues() {
    191185      size = 0; height = 0;
    192       prefixForm = null; postfixForm = null;
    193186      if (parent != null) parent.ResetCachedValues();
    194187    }
  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Symbols/ReadOnlySymbol.cs

    r3993 r3997  
    3434  [Item("ReadOnlySymbol", "Represents a symbol in a symbolic function tree that cannot be modified.")]
    3535  public abstract class ReadOnlySymbol : Symbol {
    36     #region Properties
    37     [Storable]
    38     private double initialFrequency;
    39     public double InitialFrequency {
    40       get { return initialFrequency; }
    41       set { throw new NotSupportedException(); }
    42     }
    43     #endregion
     36    //#region Properties
     37    //[Storable]
     38    //private double initialFrequency;
     39    //public double InitialFrequency {
     40    //  get { return initialFrequency; }
     41    //  set { throw new NotSupportedException(); }
     42    //}
     43    //#endregion
    4444
    4545    public override bool CanChangeName {
  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Symbols/StartSymbol.cs

    r3824 r3997  
    2525namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Symbols {
    2626  [StorableClass]
    27   [Item("StartSymbol", "Special symbol that represents the starting node of the result producing branch of a symbolic expression tree.")]
     27  [Item(StartSymbol.StartSymbolName, StartSymbol.StartSymbolDescription)]
    2828  public sealed class StartSymbol : ReadOnlySymbol {
     29    public const string StartSymbolName = "StartSymbol";
     30    public const string StartSymbolDescription = "Special symbol that represents the starting node of the result producing branch of a symbolic expression tree.";
     31
     32    public StartSymbol() : base(StartSymbol.StartSymbolName, StartSymbol.StartSymbolDescription) { }
     33    [StorableConstructor]
     34    private StartSymbol(bool deserializing) : base(deserializing) { }
    2935
    3036    public override SymbolicExpressionTreeNode CreateTreeNode() {
Note: See TracChangeset for help on using the changeset viewer.