source: trunk/sources/HeuristicLab.Problems.GeneticProgramming/3.3/Boolean/MultiplexerProblem.cs @ 12938

Last change on this file since 12938 was 12938, checked in by gkronber, 4 years ago

#2472: added even parity and multiplexer problems (GP)

File size: 8.1 KB
RevLine 
[12938]1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2015 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
22using System;
23using System.Collections.Generic;
24using System.Diagnostics.Contracts;
25using System.Linq;
26using HeuristicLab.Common;
27using HeuristicLab.Core;
28using HeuristicLab.Data;
29using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
30using HeuristicLab.Parameters;
31using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
32
33
34namespace HeuristicLab.Problems.GeneticProgramming.Boolean {
35  [Item("Multiplexer Problem",
36    "The Boolean multiplexer genetic programming problem. See Koza 1992, page 171, section 7.4.1 11-multiplexer.")]
37  [Creatable(CreatableAttribute.Categories.GeneticProgrammingProblems, Priority = 900)]
38  [StorableClass]
39  public sealed class MultiplexerProblem : SymbolicExpressionTreeProblem {
40
41    #region parameter names
42
43    private const string NumberOfBitsParameterName = "NumberOfBits";
44
45    #endregion
46
47    #region Parameter Properties
48
49    public IFixedValueParameter<IntValue> NumberOfBitsParameter {
50      get { return (IFixedValueParameter<IntValue>)Parameters[NumberOfBitsParameterName]; }
51    }
52
53    #endregion
54
55    #region Properties
56
57    public int NumberOfBits {
58      get { return NumberOfBitsParameter.Value.Value; }
59      set { NumberOfBitsParameter.Value.Value = value; }
60    }
61
62
63    #endregion
64
65    public override bool Maximization {
66      get { return true; }
67    }
68
69    public MultiplexerProblem()
70      : base() {
71      Parameters.Add(new FixedValueParameter<IntValue>(NumberOfBitsParameterName,
72        "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",
73        new IntValue(11)));
74
75      var g = new SimpleSymbolicExpressionGrammar(); // will be replaced in update grammar
76      Encoding = new SymbolicExpressionTreeEncoding(g, 100, 17);
77
78      UpdateGrammar();
79      RegisterEventHandlers();
80    }
81
82    private void UpdateGrammar() {
83      var g = new SimpleSymbolicExpressionGrammar();
84      g.AddSymbols(new[] { "AND", "OR" }, 2, 2); // See Koza 1992, page 171, section 7.4.1 11-multiplexer
85      g.AddSymbols(new[] { "NOT" }, 1, 1);
86      g.AddSymbols(new[] { "IF" }, 3, 3);
87
88      // find the number of address lines and input lines
89      // e.g. 11-MUX: 3 addrBits + 8 input bits
90
91      var addrBits = (int)Math.Log(NumberOfBits, 2); // largest power of two that fits into the number of bits
92      var inputBits = NumberOfBits - addrBits;
93
94      for (int i = 0; i < addrBits; i++)
95        g.AddTerminalSymbol(string.Format("a{0}", i));
96      for (int i = 0; i < inputBits; i++)
97        g.AddTerminalSymbol(string.Format("d{0}", i));
98
99      Encoding.Grammar = g;
100    }
101
102
103    public override double Evaluate(ISymbolicExpressionTree tree, IRandom random) {
104      if (NumberOfBits <= 0) throw new NotSupportedException("Number of bits must be larger than zero.");
105      if (NumberOfBits > 40) throw new NotSupportedException("Mupltiplexer does not support problems with number of bits > 37.");
106      var bs = Enumerable.Range(0, (int)Math.Pow(2, NumberOfBits));
107      var addrBits = (int)Math.Log(NumberOfBits, 2); // largest power of two that fits into the number of bits
108      var inputBits = NumberOfBits - addrBits;
109      var targets = bs.Select(b => CalcTarget(b, addrBits, inputBits));
110      var pred = Interpret(tree, bs, (byte)addrBits);
111      return targets.Zip(pred, (t, p) => t == p ? 1 : 0).Sum(); // count number of correct predictions
112    }
113
114    private bool CalcTarget(int b, int addrBits, int inputBits) {
115      Contract.Assert(addrBits > 0);
116      // calc addr
117      int addr = 0;
118      for (int i = addrBits - 1; i >= 0; i--) {
119        addr = addr << 1;
120        if (GetBits(b, (byte)i)) addr += 1;
121      }
122      if (addr <= inputBits)
123        return GetBits(b, (byte)(addrBits + addr));
124      else return false; // in case the number of bits is smaller then necessary we assume that the remaining lines are false
125    }
126
127    private static IEnumerable<bool> Interpret(ISymbolicExpressionTree tree, IEnumerable<int> bs, byte addrBits) {
128      // skip programRoot and startSymbol
129      return InterpretRec(tree.Root.GetSubtree(0).GetSubtree(0), bs, addrBits);
130    }
131
132
133    private static IEnumerable<bool> InterpretRec(ISymbolicExpressionTreeNode node, IEnumerable<int> bs, byte addrBits) {
134      Func<ISymbolicExpressionTreeNode, Func<bool, bool>, IEnumerable<bool>> eval1 =
135        (child, f) => InterpretRec(child, bs, addrBits).Select(f);
136      Func<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode, Func<bool, bool, bool>, IEnumerable<bool>> eval2 =
137        (left, right, f) => InterpretRec(left, bs, addrBits).Zip(InterpretRec(right, bs, addrBits), f);
138
139      switch (node.Symbol.Name) {
140        case "AND": return eval2(node.GetSubtree(0), node.GetSubtree(1), (x, y) => x & y);
141        case "OR": return eval2(node.GetSubtree(0), node.GetSubtree(1), (x, y) => x | y);
142        case "NOT": return eval1(node.GetSubtree(0), (x) => !x);
143        case "IF": return EvalIf(node.GetSubtree(0), node.GetSubtree(1), node.GetSubtree(2), bs, addrBits);
144        default: {
145            if (node.Symbol.Name[0] == 'a') {
146              byte bitPos;
147              if (byte.TryParse(node.Symbol.Name.Substring(1), out bitPos)) {
148                return bs.Select(b => GetBits(b, bitPos));
149              }
150            } else if (node.Symbol.Name[0] == 'd') {
151              byte bitPos;
152              if (byte.TryParse(node.Symbol.Name.Substring(1), out bitPos)) {
153                return bs.Select(b => GetBits(b, (byte)(bitPos + addrBits))); // offset of input line bits
154              }
155            }
156
157            throw new NotSupportedException(string.Format("Found unexpected symbol {0}", node.Symbol.Name));
158          }
159      }
160    }
161
162    private static IEnumerable<bool> EvalIf(ISymbolicExpressionTreeNode pred, ISymbolicExpressionTreeNode trueBranch, ISymbolicExpressionTreeNode falseBranch, IEnumerable<int> bs, byte addrBits) {
163      var preds = InterpretRec(pred, bs, addrBits).GetEnumerator();
164      var tB = InterpretRec(trueBranch, bs, addrBits).GetEnumerator();
165      var fB = InterpretRec(falseBranch, bs, addrBits).GetEnumerator();
166      // start enumerators
167
168      while (preds.MoveNext() & tB.MoveNext() & fB.MoveNext()) {
169        if (preds.Current) yield return tB.Current;
170        else yield return fB.Current;
171      }
172    }
173
174    private static bool GetBits(int b, byte bitPos) {
175      return (b & (1 << bitPos)) != 0;
176    }
177
178    #region item cloning and persistence
179    // persistence
180    [StorableConstructor]
181    private MultiplexerProblem(bool deserializing) : base(deserializing) { }
182
183    [StorableHook(HookType.AfterDeserialization)]
184    private void AfterDeserialization() {
185      RegisterEventHandlers();
186    }
187
188    // cloning
189    private MultiplexerProblem(MultiplexerProblem original, Cloner cloner)
190      : base(original, cloner) {
191      RegisterEventHandlers();
192    }
193    public override IDeepCloneable Clone(Cloner cloner) {
194      return new MultiplexerProblem(this, cloner);
195    }
196    #endregion
197
198    #region events
199
200    private void RegisterEventHandlers() {
201      NumberOfBitsParameter.Value.ValueChanged += (sender, args) => UpdateGrammar();
202    }
203    #endregion
204  }
205}
Note: See TracBrowser for help on using the repository browser.