Free cookie consent management tool by TermsFeed Policy Generator

Changeset 5411


Ignore:
Timestamp:
02/03/11 13:47:16 (14 years ago)
Author:
gkronber
Message:

Improved test cases for symbolic expression tree encoding and fixed minor bugs. #1336

Location:
trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3
Files:
8 edited

Legend:

Unmodified
Added
Removed
  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/ArchitectureManipulators/SubroutineDeleter.cs

    r4722 r5411  
    2828using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Symbols;
    2929using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     30using System.Collections.Generic;
    3031
    3132namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ArchitectureManipulators {
     
    9798        // deletion by random regeneration
    9899        SymbolicExpressionTreeNode replacementTree = null;
    99         // TODO: should weight symbols by tickets
    100         var selectedSymbol = invocationCutPoint.Parent.GetAllowedSymbols(invocationCutPoint.ReplacedChildIndex).SelectRandom(random);
     100        var allowedSymbolsList = invocationCutPoint.Parent.GetAllowedSymbols(invocationCutPoint.ReplacedChildIndex).ToList();
     101        var weights = allowedSymbolsList.Select(s => s.InitialFrequency);
     102        var selectedSymbol = allowedSymbolsList.SelectRandom(weights, random);
    101103
    102104        int minPossibleSize = invocationCutPoint.Parent.Grammar.GetMinExpressionLength(selectedSymbol);
  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/EnumerableExtensions.cs

    r4068 r5411  
    2323using System.Linq;
    2424using HeuristicLab.Core;
     25using System;
    2526
    2627namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
     
    3536      }
    3637    }
     38    public static T SelectRandom<T>(this IEnumerable<T> xs, IEnumerable<double> weights, IRandom random) {
     39      var list = xs as IList<T>;
     40      var weightsList = weights as IList<double>;
     41      if (list == null) {
     42        list = xs.ToList();
     43      }
     44      if (weightsList == null) {
     45        weightsList = weights.ToList();
     46      }
     47      if (list.Count != weightsList.Count) throw new ArgumentException("Number of elements in enumerations doesn't match.");
     48      if (list.Count == 0) throw new ArgumentException("Enumeration is empty", "xs");
     49
     50      double sum = weightsList.Sum();
     51      double r = random.NextDouble() * sum;
     52      double agg = 0;
     53      for (int i = 0; i < list.Count; i++) {
     54        agg += weightsList[i];
     55        if (agg > r) return list[i];
     56      }
     57      // should never happen
     58      throw new InvalidOperationException();
     59    }
    3760  }
    3861}
  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/SymbolicExpressionTreeNode.cs

    r5015 r5411  
    3737
    3838    // cached values to prevent unnecessary tree iterations
    39     private short size;
    40     private short height;
     39    private ushort size;
     40    private ushort height;
    4141
    4242    public Symbol Symbol {
     
    106106        if (SubTrees != null) {
    107107          for (int i = 0; i < SubTrees.Count; i++) {
    108             checked { size += (short)SubTrees[i].GetSize(); }
     108            checked { size += (ushort)SubTrees[i].GetSize(); }
    109109          }
    110110        }
     
    117117      else {
    118118        if (SubTrees != null) {
    119           for (int i = 0; i < SubTrees.Count; i++) height = Math.Max(height, (short)SubTrees[i].GetHeight());
     119          for (int i = 0; i < SubTrees.Count; i++) height = Math.Max(height, (ushort)SubTrees[i].GetHeight());
    120120        }
    121121        height++;
  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Tests/AllArchitectureAlteringOperatorsTest.cs

    r5367 r5411  
    8080            bool success = false;
    8181            op.ModifyArchitecture(random, selectedTree, grammar, maxTreeSize, maxTreeHeigth, maxDefuns, maxArgs, out success);
    82             if (!success) failedEvents++;
     82            if (!success) failedEvents++; // architecture manipulation might fail
    8383            Util.IsValid(selectedTree);
    8484            newTrees.Add(selectedTree);
     
    9393            bool success;
    9494            newTrees.Add(SubtreeCrossover.Cross(random, par0, par1, 0.9, MAX_TREE_SIZE, MAX_TREE_HEIGHT, out success));
    95             Assert.IsTrue(success);
     95            Assert.IsTrue(success); // crossover must succeed
    9696          }
    9797        }
     
    102102      Console.WriteLine("AllArchitectureAlteringOperators: " + Environment.NewLine +
    103103        "Operations / s: ~" + Math.Round(1000.0 / (msPerOperation)) + "operations / s)" + Environment.NewLine +
    104         "Failed events: " + failedEvents / (double)(POPULATION_SIZE * N_ITERATIONS) + "%" + Environment.NewLine +
     104        "Failed events: " + failedEvents * 100.0 / (double)(POPULATION_SIZE * N_ITERATIONS * 2.0) + "%" + Environment.NewLine +
    105105        Util.GetSizeDistributionString(trees, 200, 5) + Environment.NewLine +
    106106        Util.GetFunctionDistributionString(trees) + Environment.NewLine +
     
    108108        Util.GetTerminalDistributionString(trees) + Environment.NewLine
    109109        );
     110
     111      Assert.IsTrue(failedEvents * 100.0 / (POPULATION_SIZE * N_ITERATIONS * 2.0) < 25.0); // 75% of architecture operations must succeed
     112      Assert.IsTrue(Math.Round(1000.0 / (msPerOperation)) > 1000); // must achieve more than 1000 ops per second
    110113    }
    111114  }
  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Tests/ArgumentCreaterTest.cs

    r5367 r5411  
    5656      var grammar = Grammars.CreateArithmeticAndAdfGrammar();
    5757      var random = new MersenneTwister(31415);
     58      int failedOps = 0;
    5859      for (int i = 0; i < POPULATION_SIZE; i++) {
    5960        SymbolicExpressionTree tree;
     
    6162          tree = ProbabilisticTreeCreator.Create(random, grammar, MAX_TREE_SIZE, MAX_TREE_HEIGHT, 3, 3);
    6263        } while (!TreeHasAdfWithParameter(tree, 3));
    63         var success = ArgumentCreater.CreateNewArgument(random, tree, grammar, 10000, 100, 3, 3);
    64         Assert.IsTrue(success);
     64        var success = ArgumentCreater.CreateNewArgument(random, tree, grammar, 60000, 100, 3, 3);
     65        if (!success) failedOps++;
    6566        Util.IsValid(tree);
    6667        trees.Add(tree);
    6768      }
     69      // difficult to make sure that create argument operations succeed because trees are macro-expanded can potentially become very big
     70      // => just test if only a small proportion fails
     71      Assert.IsTrue(failedOps < POPULATION_SIZE * 0.01 ); // only 1% may fail
    6872      Console.WriteLine("ArgumentCreator: " + Environment.NewLine +
     73        "Failed operations: " + failedOps * 100.0 / POPULATION_SIZE + " %" + Environment.NewLine +
    6974        Util.GetSizeDistributionString(trees, 200, 20) + Environment.NewLine +
    7075        Util.GetFunctionDistributionString(trees) + Environment.NewLine +
  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Tests/Grammars.cs

    r4722 r5411  
    7979        var mul = new Multiplication();
    8080        var div = new Division();
     81        div.InitialFrequency = 0.0; // disable division symbol
    8182        var terminal = new Terminal();
    8283
  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Tests/SubtreeCrossoverTest.cs

    r5367 r5411  
    8686        Util.GetTerminalDistributionString(trees) + Environment.NewLine
    8787        );
     88
     89      Assert.IsTrue(Math.Round(1000.0 / (msPerCrossoverEvent)) > 2000); // must achieve more than 2000 x-overs/s
    8890    }
    8991  }
  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Tests/Util.cs

    r4722 r5411  
    130130      }
    131131      //Assert.AreEqual(tree.Root.Symbol, tree.Root.Grammar.StartSymbol);
    132       //foreach (var subtree in tree.Root.SubTrees)
    133       //  Assert.AreNotSame(subtree.Grammar, tree.Root.Grammar);
     132      foreach (var subtree in tree.Root.SubTrees)
     133        Assert.AreNotSame(subtree.Grammar, tree.Root.Grammar);
    134134      IsValid(tree.Root);
    135135    }
     
    141141      Assert.IsTrue(treeNode.SubTrees.Count >= treeNode.Grammar.GetMinSubtreeCount(matchingSymbol));
    142142      Assert.IsTrue(treeNode.SubTrees.Count <= treeNode.Grammar.GetMaxSubtreeCount(matchingSymbol));
     143      Assert.AreNotEqual(0.0, matchingSymbol.InitialFrequency); // check that no deactivated symbols occur in the tree
    143144      for (int i = 0; i < treeNode.SubTrees.Count; i++) {
    144145        Assert.IsTrue(treeNode.GetAllowedSymbols(i).Select(x => x.Name).Contains(treeNode.SubTrees[i].Symbol.Name));
Note: See TracChangeset for help on using the changeset viewer.