Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Tests/SubtreeCrossoverTest.cs @ 3297

Last change on this file since 3297 was 3297, checked in by gkronber, 12 years ago

Added test classes for crossover and subroutine creater. #290 (Implement ADFs)

File size: 7.2 KB
Line 
1using System;
2using System.Text;
3using System.Collections.Generic;
4using System.Linq;
5using Microsoft.VisualStudio.TestTools.UnitTesting;
6using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
7using HeuristicLab.Random;
8using System.Diagnostics;
9
10namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding_3._3.Tests {
11  [TestClass]
12  public class SubtreeCrossoverTest {
13    public SubtreeCrossoverTest() {
14    }
15
16    private TestContext testContextInstance;
17
18    /// <summary>
19    ///Gets or sets the test context which provides
20    ///information about and functionality for the current test run.
21    ///</summary>
22    public TestContext TestContext {
23      get {
24        return testContextInstance;
25      }
26      set {
27        testContextInstance = value;
28      }
29    }
30
31    [ClassInitialize()]
32    public static void SubtreeCrossoverTestInitialize(TestContext testContext) {
33      crossoverTrees = new List<SymbolicExpressionTree>();
34      int populationSize = 1000;
35      int generations = 5;
36      var grammar = new TestGrammar();
37      var random = new MersenneTwister();
38      for (int i = 0; i < populationSize; i++) {
39        crossoverTrees.Add(ProbabilisticTreeCreator.Create(random, grammar, 100, 10));
40      }
41      Stopwatch stopwatch = new Stopwatch();
42      stopwatch.Start();
43      for (int gCount = 0; gCount < generations; gCount++) {
44        var newPopulation = new List<SymbolicExpressionTree>();
45        for (int i = 0; i < populationSize; i++) {
46          var par0 = (SymbolicExpressionTree)crossoverTrees[random.Next(populationSize)].Clone();
47          var par1 = (SymbolicExpressionTree)crossoverTrees[random.Next(populationSize)].Clone();
48          bool success;
49          newPopulation.Add(SubtreeCrossover.Cross(random, grammar, par0, par1, 0.9, 100, 10, out success));
50        }
51        crossoverTrees = newPopulation;
52      }
53      stopwatch.Stop();
54      foreach (var tree in crossoverTrees)
55        Assert.IsTrue(grammar.IsValidExpression(tree));
56      msPerCrossoverEvent = stopwatch.ElapsedMilliseconds / (double)populationSize / (double)generations;
57    }
58
59
60
61    private static List<SymbolicExpressionTree> crossoverTrees;
62    private static double msPerCrossoverEvent;
63
64    private class Addition : Symbol { }
65    private class Subtraction : Symbol { }
66    private class Multiplication : Symbol { }
67    private class Division : Symbol { }
68    private class Terminal : Symbol { }
69
70    private class TestGrammar : DefaultSymbolicExpressionGrammar {
71      public TestGrammar()
72        : base(0, 0, 0, 0) {
73        Initialize();
74      }
75
76      private void Initialize() {
77        var add = new Addition();
78        var sub = new Subtraction();
79        var mul = new Multiplication();
80        var div = new Division();
81        var terminal = new Terminal();
82
83        var allSymbols = new List<Symbol>() { add, sub, mul, div, terminal };
84        var functionSymbols = new List<Symbol>() { add, sub, mul, div };
85        allSymbols.ForEach(s => AddAllowedSymbols(StartSymbol, 0, s));
86
87        SetMinSubTreeCount(terminal, 0);
88        SetMaxSubTreeCount(terminal, 0);
89        int maxSubTrees = 3;
90        foreach (var functionSymbol in functionSymbols) {
91          SetMinSubTreeCount(functionSymbol, 1);
92          SetMaxSubTreeCount(functionSymbol, maxSubTrees);
93          foreach (var childSymbol in allSymbols) {
94            for (int argumentIndex = 0; argumentIndex < maxSubTrees; argumentIndex++) {
95              AddAllowedSymbols(functionSymbol, argumentIndex, childSymbol);
96            }
97          }
98        }
99      }
100    }
101
102    [TestMethod()]
103    public void SubtreeCrossoverSpeed() {
104      Assert.Inconclusive(msPerCrossoverEvent + " ms per crossover event (~" +
105        Math.Round(1000.0 / (msPerCrossoverEvent)) + "crossovers / s)");
106    }
107
108    [TestMethod()]
109    public void SubtreeCrossoverSizeDistributionTest() {
110      int[] histogram = new int[105 / 5];
111      for (int i = 0; i < crossoverTrees.Count; i++) {
112        histogram[crossoverTrees[i].Size / 5]++;
113      }
114      StringBuilder strBuilder = new StringBuilder();
115      for (int i = 0; i < histogram.Length; i++) {
116        strBuilder.Append(Environment.NewLine);
117        strBuilder.Append("< "); strBuilder.Append((i + 1) * 5);
118        strBuilder.Append(": "); strBuilder.AppendFormat("{0:#0.00%}", histogram[i] / (double)crossoverTrees.Count);
119      }
120      Assert.Inconclusive("Size distribution of SubtreeCrossover: " + strBuilder);
121    }
122
123    [TestMethod()]
124    public void SubtreeCrossoverFunctionDistributionTest() {
125      Dictionary<Symbol, int> occurances = new Dictionary<Symbol, int>();
126      double n = 0.0;
127      for (int i = 0; i < crossoverTrees.Count; i++) {
128        foreach (var node in crossoverTrees[i].IterateNodesPrefix()) {
129          if (node.SubTrees.Count > 0) {
130            if (!occurances.ContainsKey(node.Symbol))
131              occurances[node.Symbol] = 0;
132            occurances[node.Symbol]++;
133            n++;
134          }
135        }
136      }
137      StringBuilder strBuilder = new StringBuilder();
138      foreach (var function in occurances.Keys) {
139        strBuilder.Append(Environment.NewLine);
140        strBuilder.Append(function.Name); strBuilder.Append(": ");
141        strBuilder.AppendFormat("{0:#0.00%}", occurances[function] / n);
142      }
143      Assert.Inconclusive("Function distribution of SubtreeCrossover: " + strBuilder);
144    }
145
146    [TestMethod()]
147    public void SubtreeCrossoverNumberOfSubTreesDistributionTest() {
148      Dictionary<int, int> occurances = new Dictionary<int, int>();
149      double n = 0.0;
150      for (int i = 0; i < crossoverTrees.Count; i++) {
151        foreach (var node in crossoverTrees[i].IterateNodesPrefix()) {
152          if (!occurances.ContainsKey(node.SubTrees.Count))
153            occurances[node.SubTrees.Count] = 0;
154          occurances[node.SubTrees.Count]++;
155          n++;
156        }
157      }
158      StringBuilder strBuilder = new StringBuilder();
159      foreach (var arity in occurances.Keys) {
160        strBuilder.Append(Environment.NewLine);
161        strBuilder.Append(arity); strBuilder.Append(": ");
162        strBuilder.AppendFormat("{0:#0.00%}", occurances[arity] / n);
163      }
164      Assert.Inconclusive("Distribution of function arities of SubtreeCrossover: " + strBuilder);
165    }
166
167
168    [TestMethod()]
169    public void SubtreeCrossoverTerminalDistributionTest() {
170      Dictionary<Symbol, int> occurances = new Dictionary<Symbol, int>();
171      double n = 0.0;
172      for (int i = 0; i < crossoverTrees.Count; i++) {
173        foreach (var node in crossoverTrees[i].IterateNodesPrefix()) {
174          if (node.SubTrees.Count == 0) {
175            if (!occurances.ContainsKey(node.Symbol))
176              occurances[node.Symbol] = 0;
177            occurances[node.Symbol]++;
178            n++;
179          }
180        }
181      }
182      StringBuilder strBuilder = new StringBuilder();
183      foreach (var function in occurances.Keys) {
184        strBuilder.Append(Environment.NewLine);
185        strBuilder.Append(function.Name); strBuilder.Append(": ");
186        strBuilder.AppendFormat("{0:#0.00%}", occurances[function] / n);
187      }
188      Assert.Inconclusive("Terminal distribution of SubtreeCrossover: " + strBuilder);
189    }
190  }
191}
Note: See TracBrowser for help on using the repository browser.