Free cookie consent management tool by TermsFeed Policy Generator

Changeset 3997


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
Files:
1 added
9 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() {

  • trunk/sources/HeuristicLab.Problems.DataAnalysis.Regression/3.3/Analyzers/RegressionSolutionAnalyzer.cs

    r3996 r3997  
    3535using HeuristicLab.Problems.DataAnalysis;
    3636using HeuristicLab.Problems.DataAnalysis.Evaluators;
     37using System;
    3738
    3839namespace HeuristicLab.Problems.DataAnalysis.Regression.Symbolic.Analyzers {

  • trunk/sources/HeuristicLab.Problems.DataAnalysis/3.3/Symbolic/Symbols/ConstantTreeNode.cs

    r3512 r3997  
    6565    public override void ShakeLocalParameters(IRandom random, double shakingFactor) {
    6666      base.ShakeLocalParameters(random, shakingFactor);
    67       var normalDistributedRNG = new NormalDistributedRandom(random, Symbol.ManipulatorNu, Symbol.ManipulatorSigma);
    68       double x = normalDistributedRNG.NextDouble();
     67      double x = NormalDistributedRandom.NextDouble(random, Symbol.ManipulatorNu, Symbol.ManipulatorSigma);
    6968      Value = Value + x * shakingFactor;
    7069    }

  • trunk/sources/HeuristicLab.Problems.DataAnalysis/3.3/Symbolic/Symbols/LaggedVariableTreeNode.cs

    r3841 r3997  
    7373    public override void ResetLocalParameters(IRandom random) {
    7474      base.ResetLocalParameters(random);
    75       var normalDistributedRNG = new NormalDistributedRandom(random, Symbol.WeightNu, Symbol.WeightSigma);
    76       weight = normalDistributedRNG.NextDouble();
     75      weight = NormalDistributedRandom.NextDouble(random, Symbol.WeightNu, Symbol.WeightSigma);
    7776      variableName = Symbol.VariableNames.SelectRandom(random);
    7877      lag = random.Next(Symbol.MinLag, Symbol.MaxLag + 1);
    … …  
    8180    public override void ShakeLocalParameters(IRandom random, double shakingFactor) {
    8281      base.ShakeLocalParameters(random, shakingFactor);
    83       var normalDistributedRNG = new NormalDistributedRandom(random, Symbol.WeightManipulatorNu, Symbol.WeightManipulatorSigma);
    84       double x = normalDistributedRNG.NextDouble();
     82      double x = NormalDistributedRandom.NextDouble(random, Symbol.WeightManipulatorNu, Symbol.WeightManipulatorSigma);
    8583      weight = weight + x * shakingFactor;
    8684      variableName = Symbol.VariableNames.SelectRandom(random);

  • trunk/sources/HeuristicLab.Problems.DataAnalysis/3.3/Symbolic/Symbols/VariableTreeNode.cs

    r3512 r3997  
    6767    public override void ResetLocalParameters(IRandom random) {
    6868      base.ResetLocalParameters(random);
    69       var normalDistributedRNG = new NormalDistributedRandom(random, Symbol.WeightNu, Symbol.WeightSigma);
    70       weight = normalDistributedRNG.NextDouble();
     69      weight = NormalDistributedRandom.NextDouble(random, Symbol.WeightNu, Symbol.WeightSigma);
    7170      variableName = Symbol.VariableNames.SelectRandom(random);
    7271    }
    … …  
    7473    public override void ShakeLocalParameters(IRandom random, double shakingFactor) {
    7574      base.ShakeLocalParameters(random, shakingFactor);
    76       var normalDistributedRNG = new NormalDistributedRandom(random, Symbol.WeightManipulatorNu, Symbol.WeightManipulatorSigma);
    77       double x = normalDistributedRNG.NextDouble();
     75      double x = NormalDistributedRandom.NextDouble(random, Symbol.WeightManipulatorNu, Symbol.WeightManipulatorSigma);
    7876      weight = weight + x * shakingFactor;
    7977      variableName = Symbol.VariableNames.SelectRandom(random);

  • trunk/sources/HeuristicLab.Random/3.3/NormalDistributedRandom.cs

    r3376 r3997  
    5858    private IRandom uniform;
    5959
    60     private double[] w = new double[] {
     60    private static double[] w = new double[] {
    6161      1.7290404664e-09,
    6262      1.2680928529e-10,
    … …  
    188188      1.6030947680e-09
    189189    };
    190     private long[] k = new long[] {
     190    private static long[] k = new long[] {
    191191      1991057938,
    192192      0,
    … …  
    318318      2010539237
    319319   };
    320     private double[] f = new double[] {
     320    private static double[] f = new double[] {
    321321      1.0000000000e+00,
    322322      9.6359968185e-01,
    … …  
    510510    /// <returns>A double random number.</returns>
    511511    public double NextDouble() {
    512       double signFactor = uniform.Next() % 2 == 0 ? 1.0 : -1.0;
    513       return sigma * signFactor * NextPositiveDouble() + mu;
    514     }
    515 
    516     private double NextPositiveDouble() {
    517       int j = uniform.Next();
    518       int i = (j & 127);
    519       if (Math.Abs(j) < k[i]) {
    520         return j * w[i];
    521       } else {
    522         double r = 3.442620;
    523         double x, y;
    524         x = j * w[i];
    525         if (i == 0) {
    526           do {
    527             x = -Math.Log(ScaledUniform()) * 0.2904764;
    528             y = -Math.Log(ScaledUniform());
    529           } while (y + y < x * x);
    530           return (j > 0) ? r + x : -r - x;
    531         }
    532         if (f[i] + ScaledUniform() * (f[i - 1] - f[i]) < Math.Exp(-0.5 * x * x)) {
    533           return x;
    534         } else {
    535           // recurse
    536           return (NextPositiveDouble());
    537         }
    538       }
    539     }
    540 
    541     private double ScaledUniform() {
    542       return 0.5 + uniform.Next() * 0.2328306e-9;
    543     }
    544 
     512      return NormalDistributedRandom.NextDouble(uniform, mu, sigma);
     513    }
    545514
    546515    #endregion
    … …  
    560529      return clone;
    561530    }
     531
     532    public static double NextDouble(IRandom uniformRandom, double mu, double sigma) {
     533      double signFactor = uniformRandom.Next() % 2 == 0 ? 1.0 : -1.0;
     534      return sigma * signFactor * NextPositiveDouble(uniformRandom) + mu;
     535    }
     536
     537    private static double NextPositiveDouble(IRandom uniformRandom) {
     538      int j = uniformRandom.Next();
     539      int i = (j & 127);
     540      if (Math.Abs(j) < k[i]) {
     541        return j * w[i];
     542      } else {
     543        double r = 3.442620;
     544        double x, y;
     545        x = j * w[i];
     546        if (i == 0) {
     547          do {
     548            x = -Math.Log(ScaledUniform(uniformRandom)) * 0.2904764;
     549            y = -Math.Log(ScaledUniform(uniformRandom));
     550          } while (y + y < x * x);
     551          return (j > 0) ? r + x : -r - x;
     552        }
     553        if (f[i] + ScaledUniform(uniformRandom) * (f[i - 1] - f[i]) < Math.Exp(-0.5 * x * x)) {
     554          return x;
     555        } else {
     556          // recurse
     557          return (NextPositiveDouble(uniformRandom));
     558        }
     559      }
     560    }
     561
     562    private static double ScaledUniform(IRandom uniformRandom) {
     563      return 0.5 + uniformRandom.Next() * 0.2328306e-9;
     564    }
    562565  }
    563566}
Note: See TracChangeset for help on using the changeset viewer.