Index: trunk/sources/HeuristicLab.Problems.GeneticProgramming/3.3/Boolean/EvenParityProblem.cs
===================================================================
--- trunk/sources/HeuristicLab.Problems.GeneticProgramming/3.3/Boolean/EvenParityProblem.cs	(revision 12938)
+++ trunk/sources/HeuristicLab.Problems.GeneticProgramming/3.3/Boolean/EvenParityProblem.cs	(revision 12938)
@@ -0,0 +1,160 @@
+#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ *
+ * This file is part of HeuristicLab.
+ *
+ * HeuristicLab is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * HeuristicLab is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
+ */
+#endregion
+
+using System;
+using System.Collections.Generic;
+using System.Linq;
+using HeuristicLab.Common;
+using HeuristicLab.Core;
+using HeuristicLab.Data;
+using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
+using HeuristicLab.Parameters;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+
+
+namespace HeuristicLab.Problems.GeneticProgramming.Boolean {
+  [Item("Even Parity Problem", "The Boolean even parity genetic programming problem. See Koza, 1992, page 529 section 20.2 Symbolic Regression of Even-Parity Functions")]
+  [Creatable(CreatableAttribute.Categories.GeneticProgrammingProblems, Priority = 900)]
+  [StorableClass]
+  public sealed class EvenParityProblem : SymbolicExpressionTreeProblem {
+
+    #region parameter names
+
+    private const string NumberOfBitsParameterName = "NumberOfBits";
+
+    #endregion
+
+    #region Parameter Properties
+    public IFixedValueParameter<IntValue> NumberOfBitsParameter {
+      get { return (IFixedValueParameter<IntValue>)Parameters[NumberOfBitsParameterName]; }
+    }
+
+    #endregion
+
+    #region Properties
+
+    public int NumberOfBits {
+      get { return NumberOfBitsParameter.Value.Value; }
+      set { NumberOfBitsParameter.Value.Value = value; }
+    }
+
+
+    #endregion
+
+    public override bool Maximization {
+      get { return true; }
+    }
+
+    public EvenParityProblem()
+      : base() {
+      Parameters.Add(new FixedValueParameter<IntValue>(NumberOfBitsParameterName, "The number of bits for the input parameter for the even parity function", new IntValue(4)));
+
+      var g = new SimpleSymbolicExpressionGrammar(); // will be replaced in update grammar
+      Encoding = new SymbolicExpressionTreeEncoding(g, 100, 17);
+
+      UpdateGrammar();
+      RegisterEventHandlers();
+    }
+
+    private void UpdateGrammar() {
+      var g = new SimpleSymbolicExpressionGrammar();
+      g.AddSymbols(new[] { "AND", "OR", "NAND", "NOR" }, 2, 2); // see Koza, 1992, page 529 section 20.2 Symbolic Regression of Even-Parity Functions
+
+      // add one terminal symbol for each bit
+      for (int i = 0; i < NumberOfBits; i++)
+        g.AddTerminalSymbol(string.Format("{0}", i));
+
+      Encoding.Grammar = g;
+    }
+
+
+    public override double Evaluate(ISymbolicExpressionTree tree, IRandom random) {
+      if (NumberOfBits <= 0) throw new NotSupportedException("Number of bits must be larger than zero.");
+      if (NumberOfBits > 10) throw new NotSupportedException("Even parity does not support problems with number of bits > 10.");
+      var bs = Enumerable.Range(0, (int)Math.Pow(2, NumberOfBits));
+      var targets = bs.Select(b => CalcTarget(b, NumberOfBits));
+      var pred = Interpret(tree, bs);
+      return targets.Zip(pred, (t, p) => t == p ? 1 : 0).Sum(); // count number of correct predictions
+    }
+
+    private static bool CalcTarget(int b, int numBits) {
+      bool res = GetBits(b, 0);
+      for (byte i = 1; i < numBits; i++)
+        res = res ^ GetBits(b, i); // XOR
+      return res;
+    }
+
+    private static IEnumerable<bool> Interpret(ISymbolicExpressionTree tree, IEnumerable<int> bs) {
+      // skip programRoot and startSymbol
+      return InterpretRec(tree.Root.GetSubtree(0).GetSubtree(0), bs);
+    }
+
+
+    private static IEnumerable<bool> InterpretRec(ISymbolicExpressionTreeNode node, IEnumerable<int> bs) {
+      Func<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode, Func<bool, bool, bool>, IEnumerable<bool>> eval2 =
+        (left, right, f) => InterpretRec(left, bs).Zip(InterpretRec(right, bs), f);
+
+      switch (node.Symbol.Name) {
+        case "AND": return eval2(node.GetSubtree(0), node.GetSubtree(1), (x, y) => x & y);
+        case "OR": return eval2(node.GetSubtree(0), node.GetSubtree(1), (x, y) => x | y);
+        case "NAND": return eval2(node.GetSubtree(0), node.GetSubtree(1), (x, y) => !(x & y));
+        case "NOR": return eval2(node.GetSubtree(0), node.GetSubtree(1), (x, y) => !(x | y));
+        default: {
+            byte bitPos;
+            if (byte.TryParse(node.Symbol.Name, out bitPos)) {
+              return bs.Select(b => GetBits(b, bitPos));
+            } else throw new NotSupportedException(string.Format("Found unexpected symbol {0}", node.Symbol.Name));
+          }
+      }
+    }
+
+    private static bool GetBits(int b, byte bitPos) {
+      return (b & (1 << bitPos)) != 0;
+    }
+
+    #region item cloning and persistence
+    // persistence
+    [StorableConstructor]
+    private EvenParityProblem(bool deserializing) : base(deserializing) { }
+
+    [StorableHook(HookType.AfterDeserialization)]
+    private void AfterDeserialization() {
+      RegisterEventHandlers();
+    }
+
+    // cloning 
+    private EvenParityProblem(EvenParityProblem original, Cloner cloner)
+      : base(original, cloner) {
+      RegisterEventHandlers();
+    }
+    public override IDeepCloneable Clone(Cloner cloner) {
+      return new EvenParityProblem(this, cloner);
+    }
+    #endregion
+
+    #region events
+
+    private void RegisterEventHandlers() {
+      NumberOfBitsParameter.Value.ValueChanged += (sender, args) => UpdateGrammar();
+    }
+    #endregion
+  }
+}
Index: trunk/sources/HeuristicLab.Problems.GeneticProgramming/3.3/Boolean/MultiplexerProblem.cs
===================================================================
--- trunk/sources/HeuristicLab.Problems.GeneticProgramming/3.3/Boolean/MultiplexerProblem.cs	(revision 12938)
+++ trunk/sources/HeuristicLab.Problems.GeneticProgramming/3.3/Boolean/MultiplexerProblem.cs	(revision 12938)
@@ -0,0 +1,205 @@
+#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ *
+ * This file is part of HeuristicLab.
+ *
+ * HeuristicLab is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * HeuristicLab is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
+ */
+#endregion
+
+using System;
+using System.Collections.Generic;
+using System.Diagnostics.Contracts;
+using System.Linq;
+using HeuristicLab.Common;
+using HeuristicLab.Core;
+using HeuristicLab.Data;
+using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
+using HeuristicLab.Parameters;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+
+
+namespace HeuristicLab.Problems.GeneticProgramming.Boolean {
+  [Item("Multiplexer Problem",
+    "The Boolean multiplexer genetic programming problem. See Koza 1992, page 171, section 7.4.1 11-multiplexer.")]
+  [Creatable(CreatableAttribute.Categories.GeneticProgrammingProblems, Priority = 900)]
+  [StorableClass]
+  public sealed class MultiplexerProblem : SymbolicExpressionTreeProblem {
+
+    #region parameter names
+
+    private const string NumberOfBitsParameterName = "NumberOfBits";
+
+    #endregion
+
+    #region Parameter Properties
+
+    public IFixedValueParameter<IntValue> NumberOfBitsParameter {
+      get { return (IFixedValueParameter<IntValue>)Parameters[NumberOfBitsParameterName]; }
+    }
+
+    #endregion
+
+    #region Properties
+
+    public int NumberOfBits {
+      get { return NumberOfBitsParameter.Value.Value; }
+      set { NumberOfBitsParameter.Value.Value = value; }
+    }
+
+
+    #endregion
+
+    public override bool Maximization {
+      get { return true; }
+    }
+
+    public MultiplexerProblem()
+      : base() {
+      Parameters.Add(new FixedValueParameter<IntValue>(NumberOfBitsParameterName,
+        "The number of bits for the input parameter for the multiplexer function. This is the sum of the number of address bits and the number of input lines. E.g. the 11-MUX has 3 address bits and 8 input lines",
+        new IntValue(11)));
+
+      var g = new SimpleSymbolicExpressionGrammar(); // will be replaced in update grammar
+      Encoding = new SymbolicExpressionTreeEncoding(g, 100, 17);
+
+      UpdateGrammar();
+      RegisterEventHandlers();
+    }
+
+    private void UpdateGrammar() {
+      var g = new SimpleSymbolicExpressionGrammar();
+      g.AddSymbols(new[] { "AND", "OR" }, 2, 2); // See Koza 1992, page 171, section 7.4.1 11-multiplexer
+      g.AddSymbols(new[] { "NOT" }, 1, 1);
+      g.AddSymbols(new[] { "IF" }, 3, 3);
+
+      // find the number of address lines and input lines
+      // e.g. 11-MUX: 3 addrBits + 8 input bits
+
+      var addrBits = (int)Math.Log(NumberOfBits, 2); // largest power of two that fits into the number of bits
+      var inputBits = NumberOfBits - addrBits;
+
+      for (int i = 0; i < addrBits; i++)
+        g.AddTerminalSymbol(string.Format("a{0}", i));
+      for (int i = 0; i < inputBits; i++)
+        g.AddTerminalSymbol(string.Format("d{0}", i));
+
+      Encoding.Grammar = g;
+    }
+
+
+    public override double Evaluate(ISymbolicExpressionTree tree, IRandom random) {
+      if (NumberOfBits <= 0) throw new NotSupportedException("Number of bits must be larger than zero.");
+      if (NumberOfBits > 40) throw new NotSupportedException("Mupltiplexer does not support problems with number of bits > 37.");
+      var bs = Enumerable.Range(0, (int)Math.Pow(2, NumberOfBits));
+      var addrBits = (int)Math.Log(NumberOfBits, 2); // largest power of two that fits into the number of bits
+      var inputBits = NumberOfBits - addrBits;
+      var targets = bs.Select(b => CalcTarget(b, addrBits, inputBits));
+      var pred = Interpret(tree, bs, (byte)addrBits);
+      return targets.Zip(pred, (t, p) => t == p ? 1 : 0).Sum(); // count number of correct predictions
+    }
+
+    private bool CalcTarget(int b, int addrBits, int inputBits) {
+      Contract.Assert(addrBits > 0);
+      // calc addr
+      int addr = 0;
+      for (int i = addrBits - 1; i >= 0; i--) {
+        addr = addr << 1;
+        if (GetBits(b, (byte)i)) addr += 1;
+      }
+      if (addr <= inputBits)
+        return GetBits(b, (byte)(addrBits + addr));
+      else return false; // in case the number of bits is smaller then necessary we assume that the remaining lines are false
+    }
+
+    private static IEnumerable<bool> Interpret(ISymbolicExpressionTree tree, IEnumerable<int> bs, byte addrBits) {
+      // skip programRoot and startSymbol
+      return InterpretRec(tree.Root.GetSubtree(0).GetSubtree(0), bs, addrBits);
+    }
+
+
+    private static IEnumerable<bool> InterpretRec(ISymbolicExpressionTreeNode node, IEnumerable<int> bs, byte addrBits) {
+      Func<ISymbolicExpressionTreeNode, Func<bool, bool>, IEnumerable<bool>> eval1 =
+        (child, f) => InterpretRec(child, bs, addrBits).Select(f);
+      Func<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode, Func<bool, bool, bool>, IEnumerable<bool>> eval2 =
+        (left, right, f) => InterpretRec(left, bs, addrBits).Zip(InterpretRec(right, bs, addrBits), f);
+
+      switch (node.Symbol.Name) {
+        case "AND": return eval2(node.GetSubtree(0), node.GetSubtree(1), (x, y) => x & y);
+        case "OR": return eval2(node.GetSubtree(0), node.GetSubtree(1), (x, y) => x | y);
+        case "NOT": return eval1(node.GetSubtree(0), (x) => !x);
+        case "IF": return EvalIf(node.GetSubtree(0), node.GetSubtree(1), node.GetSubtree(2), bs, addrBits);
+        default: {
+            if (node.Symbol.Name[0] == 'a') {
+              byte bitPos;
+              if (byte.TryParse(node.Symbol.Name.Substring(1), out bitPos)) {
+                return bs.Select(b => GetBits(b, bitPos));
+              }
+            } else if (node.Symbol.Name[0] == 'd') {
+              byte bitPos;
+              if (byte.TryParse(node.Symbol.Name.Substring(1), out bitPos)) {
+                return bs.Select(b => GetBits(b, (byte)(bitPos + addrBits))); // offset of input line bits
+              }
+            }
+
+            throw new NotSupportedException(string.Format("Found unexpected symbol {0}", node.Symbol.Name));
+          }
+      }
+    }
+
+    private static IEnumerable<bool> EvalIf(ISymbolicExpressionTreeNode pred, ISymbolicExpressionTreeNode trueBranch, ISymbolicExpressionTreeNode falseBranch, IEnumerable<int> bs, byte addrBits) {
+      var preds = InterpretRec(pred, bs, addrBits).GetEnumerator();
+      var tB = InterpretRec(trueBranch, bs, addrBits).GetEnumerator();
+      var fB = InterpretRec(falseBranch, bs, addrBits).GetEnumerator();
+      // start enumerators
+
+      while (preds.MoveNext() & tB.MoveNext() & fB.MoveNext()) {
+        if (preds.Current) yield return tB.Current;
+        else yield return fB.Current;
+      }
+    }
+
+    private static bool GetBits(int b, byte bitPos) {
+      return (b & (1 << bitPos)) != 0;
+    }
+
+    #region item cloning and persistence
+    // persistence
+    [StorableConstructor]
+    private MultiplexerProblem(bool deserializing) : base(deserializing) { }
+
+    [StorableHook(HookType.AfterDeserialization)]
+    private void AfterDeserialization() {
+      RegisterEventHandlers();
+    }
+
+    // cloning 
+    private MultiplexerProblem(MultiplexerProblem original, Cloner cloner)
+      : base(original, cloner) {
+      RegisterEventHandlers();
+    }
+    public override IDeepCloneable Clone(Cloner cloner) {
+      return new MultiplexerProblem(this, cloner);
+    }
+    #endregion
+
+    #region events
+
+    private void RegisterEventHandlers() {
+      NumberOfBitsParameter.Value.ValueChanged += (sender, args) => UpdateGrammar();
+    }
+    #endregion
+  }
+}
Index: trunk/sources/HeuristicLab.Problems.GeneticProgramming/3.3/HeuristicLab.Problems.GeneticProgramming-3.3.csproj
===================================================================
--- trunk/sources/HeuristicLab.Problems.GeneticProgramming/3.3/HeuristicLab.Problems.GeneticProgramming-3.3.csproj	(revision 12937)
+++ trunk/sources/HeuristicLab.Problems.GeneticProgramming/3.3/HeuristicLab.Problems.GeneticProgramming-3.3.csproj	(revision 12938)
@@ -110,4 +110,6 @@
     <Compile Include="ArtificialAnt\Trail.cs" />
     <Compile Include="BasicSymbolicRegression\Problem.cs" />
+    <Compile Include="Boolean\MultiplexerProblem.cs" />
+    <Compile Include="Boolean\EvenParityProblem.cs" />
     <Compile Include="LawnMower\Interpreter.cs" />
     <Compile Include="LawnMower\Problem.cs" />
