source: stable/HeuristicLab.Problems.GeneticProgramming/3.3/Boolean/MultiplexerProblem.cs @ 17149

Last change on this file since 17149 was 17149, checked in by abeham, 2 months ago

#3005: merged to stable (16872, 16873, 16875, 16890)

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