1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)


4  *


5  * This file is part of HeuristicLab.


6  *


7  * HeuristicLab is free software: you can redistribute it and/or modify


8  * it under the terms of the GNU General Public License as published by


9  * the Free Software Foundation, either version 3 of the License, or


10  * (at your option) any later version.


11  *


12  * HeuristicLab is distributed in the hope that it will be useful,


13  * but WITHOUT ANY WARRANTY; without even the implied warranty of


14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the


15  * GNU General Public License for more details.


16  *


17  * You should have received a copy of the GNU General Public License


18  * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.


19  */


20  #endregion


21 


22  using System;


23  using System.Collections.Generic;


24  using System.Linq;


25  using HeuristicLab.Common;


26  using HeuristicLab.Core;


27  using HeuristicLab.Data;


28  using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;


29  using HeuristicLab.Parameters;


30  using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;


31 


32 


33  namespace HeuristicLab.Problems.GeneticProgramming.Boolean {


34  [Item("Even Parity Problem", "The Boolean even parity genetic programming problem. See Koza, 1992, page 529 section 20.2 Symbolic Regression of EvenParity Functions")]


35  [Creatable(CreatableAttribute.Categories.GeneticProgrammingProblems, Priority = 900)]


36  [StorableClass]


37  public sealed class EvenParityProblem : SymbolicExpressionTreeProblem {


38 


39  #region parameter names


40 


41  private const string NumberOfBitsParameterName = "NumberOfBits";


42 


43  #endregion


44 


45  #region Parameter Properties


46  public IFixedValueParameter<IntValue> NumberOfBitsParameter {


47  get { return (IFixedValueParameter<IntValue>)Parameters[NumberOfBitsParameterName]; }


48  }


49 


50  #endregion


51 


52  #region Properties


53 


54  public int NumberOfBits {


55  get { return NumberOfBitsParameter.Value.Value; }


56  set { NumberOfBitsParameter.Value.Value = value; }


57  }


58 


59 


60  #endregion


61 


62  public override bool Maximization {


63  get { return true; }


64  }


65 


66  public EvenParityProblem()


67  : base() {


68  Parameters.Add(new FixedValueParameter<IntValue>(NumberOfBitsParameterName, "The number of bits for the input parameter for the even parity function", new IntValue(4)));


69 


70  var g = new SimpleSymbolicExpressionGrammar(); // will be replaced in update grammar


71  Encoding = new SymbolicExpressionTreeEncoding(g, 100, 17);


72 


73  UpdateGrammar();


74  RegisterEventHandlers();


75  }


76 


77  private void UpdateGrammar() {


78  var g = new SimpleSymbolicExpressionGrammar();


79  g.AddSymbols(new[] { "AND", "OR", "NAND", "NOR" }, 2, 2); // see Koza, 1992, page 529 section 20.2 Symbolic Regression of EvenParity Functions


80 


81  // add one terminal symbol for each bit


82  for (int i = 0; i < NumberOfBits; i++)


83  g.AddTerminalSymbol(string.Format("{0}", i));


84 


85  Encoding.Grammar = g;


86 


87  BestKnownQuality = Math.Pow(2, NumberOfBits); // this is a benchmark problem (the best achievable quality is known for a given number of bits)


88  }


89 


90 


91  public override double Evaluate(ISymbolicExpressionTree tree, IRandom random) {


92  if (NumberOfBits <= 0) throw new NotSupportedException("Number of bits must be larger than zero.");


93  if (NumberOfBits > 10) throw new NotSupportedException("Even parity does not support problems with number of bits > 10.");


94  var bs = Enumerable.Range(0, (int)Math.Pow(2, NumberOfBits));


95  var targets = bs.Select(b => CalcTarget(b, NumberOfBits));


96  var pred = Interpret(tree, bs);


97  return targets.Zip(pred, (t, p) => t == p ? 1 : 0).Sum(); // count number of correct predictions


98  }


99 


100  private static bool CalcTarget(int b, int numBits) {


101  bool res = GetBits(b, 0);


102  for (byte i = 1; i < numBits; i++)


103  res = res ^ GetBits(b, i); // XOR


104  return res;


105  }


106 


107  private static IEnumerable<bool> Interpret(ISymbolicExpressionTree tree, IEnumerable<int> bs) {


108  // skip programRoot and startSymbol


109  return InterpretRec(tree.Root.GetSubtree(0).GetSubtree(0), bs);


110  }


111 


112 


113  private static IEnumerable<bool> InterpretRec(ISymbolicExpressionTreeNode node, IEnumerable<int> bs) {


114  Func<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode, Func<bool, bool, bool>, IEnumerable<bool>> eval2 =


115  (left, right, f) => InterpretRec(left, bs).Zip(InterpretRec(right, bs), f);


116 


117  switch (node.Symbol.Name) {


118  case "AND": return eval2(node.GetSubtree(0), node.GetSubtree(1), (x, y) => x & y);


119  case "OR": return eval2(node.GetSubtree(0), node.GetSubtree(1), (x, y) => x  y);


120  case "NAND": return eval2(node.GetSubtree(0), node.GetSubtree(1), (x, y) => !(x & y));


121  case "NOR": return eval2(node.GetSubtree(0), node.GetSubtree(1), (x, y) => !(x  y));


122  default: {


123  byte bitPos;


124  if (byte.TryParse(node.Symbol.Name, out bitPos)) {


125  return bs.Select(b => GetBits(b, bitPos));


126  } else throw new NotSupportedException(string.Format("Found unexpected symbol {0}", node.Symbol.Name));


127  }


128  }


129  }


130 


131  private static bool GetBits(int b, byte bitPos) {


132  return (b & (1 << bitPos)) != 0;


133  }


134 


135  #region item cloning and persistence


136  // persistence


137  [StorableConstructor]


138  private EvenParityProblem(bool deserializing) : base(deserializing) { }


139 


140  [StorableHook(HookType.AfterDeserialization)]


141  private void AfterDeserialization() {


142  RegisterEventHandlers();


143  }


144 


145  // cloning


146  private EvenParityProblem(EvenParityProblem original, Cloner cloner)


147  : base(original, cloner) {


148  RegisterEventHandlers();


149  }


150  public override IDeepCloneable Clone(Cloner cloner) {


151  return new EvenParityProblem(this, cloner);


152  }


153  #endregion


154 


155  #region events


156 


157  private void RegisterEventHandlers() {


158  NumberOfBitsParameter.Value.ValueChanged += (sender, args) => UpdateGrammar();


159  }


160  #endregion


161  }


162  }

