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

Last change on this file since 13267 was 13267, checked in by mkommend, 6 years ago

#2472: Minor code improvements in HL.Problems.GP (typos, code organization, code unification).

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