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

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

#2472: merged r12921,r12936:12938,r12940,r12947,r13055:13058,r13163,r13267,r13269 from trunk to stable

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",
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    #region item cloning and persistence
63    // persistence
64    [StorableConstructor]
65    private MultiplexerProblem(bool deserializing) : base(deserializing) { }
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
91      UpdateGrammar();
92      RegisterEventHandlers();
93    }
94
95    private void UpdateGrammar() {
96      var g = new SimpleSymbolicExpressionGrammar();
97      g.AddSymbols(new[] { "AND", "OR" }, 2, 2); // See Koza 1992, page 171, section 7.4.1 11-multiplexer
98      g.AddSymbols(new[] { "NOT" }, 1, 1);
99      g.AddSymbols(new[] { "IF" }, 3, 3);
100
101      // find the number of address lines and input lines
102      // e.g. 11-MUX: 3 addrBits + 8 input bits
103
104      var addrBits = (int)Math.Log(NumberOfBits, 2); // largest power of two that fits into the number of bits
105      var inputBits = NumberOfBits - addrBits;
106
107      for (int i = 0; i < addrBits; i++)
108        g.AddTerminalSymbol(string.Format("a{0}", i));
109      for (int i = 0; i < inputBits; i++)
110        g.AddTerminalSymbol(string.Format("d{0}", i));
111
112      Encoding.Grammar = g;
113
114      BestKnownQuality = Math.Pow(2, NumberOfBits); // this is a benchmark problem (the best achievable quality is known for a given number of bits)
115    }
116
117
118    public override double Evaluate(ISymbolicExpressionTree tree, IRandom random) {
119      if (NumberOfBits <= 0) throw new NotSupportedException("Number of bits must be larger than zero.");
120      if (NumberOfBits > 37) throw new NotSupportedException("Multiplexer does not support problems with number of bits > 37.");
121      var bs = Enumerable.Range(0, (int)Math.Pow(2, NumberOfBits));
122      var addrBits = (int)Math.Log(NumberOfBits, 2); // largest power of two that fits into the number of bits
123      var inputBits = NumberOfBits - addrBits;
124      var targets = bs.Select(b => CalcTarget(b, addrBits, inputBits));
125      var pred = Interpret(tree, bs, (byte)addrBits);
126      return targets.Zip(pred, (t, p) => t == p ? 1 : 0).Sum(); // count number of correct predictions
127    }
128
129    private bool CalcTarget(int b, int addrBits, int inputBits) {
130      Contract.Assert(addrBits > 0);
131      // calc addr
132      int addr = 0;
133      for (int i = addrBits - 1; i >= 0; i--) {
134        addr = addr << 1;
135        if (GetBits(b, (byte)i)) addr += 1;
136      }
137      if (addr <= inputBits)
138        return GetBits(b, (byte)(addrBits + addr));
139      else return false; // in case the number of bits is smaller then necessary we assume that the remaining lines are false
140    }
141
142    private static IEnumerable<bool> Interpret(ISymbolicExpressionTree tree, IEnumerable<int> bs, byte addrBits) {
143      // skip programRoot and startSymbol
144      return InterpretRec(tree.Root.GetSubtree(0).GetSubtree(0), bs, addrBits);
145    }
146
147
148    private static IEnumerable<bool> InterpretRec(ISymbolicExpressionTreeNode node, IEnumerable<int> bs, byte addrBits) {
149      Func<ISymbolicExpressionTreeNode, Func<bool, bool>, IEnumerable<bool>> unaryEval =
150        (child, f) => InterpretRec(child, bs, addrBits).Select(f);
151      Func<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode, Func<bool, bool, bool>, IEnumerable<bool>> binaryEval =
152        (left, right, f) => InterpretRec(left, bs, addrBits).Zip(InterpretRec(right, bs, addrBits), f);
153
154      switch (node.Symbol.Name) {
155        case "AND": return binaryEval(node.GetSubtree(0), node.GetSubtree(1), (x, y) => x & y);
156        case "OR": return binaryEval(node.GetSubtree(0), node.GetSubtree(1), (x, y) => x | y);
157        case "NOT": return unaryEval(node.GetSubtree(0), (x) => !x);
158        case "IF": return EvalIf(node.GetSubtree(0), node.GetSubtree(1), node.GetSubtree(2), bs, addrBits);
159        default: {
160            if (node.Symbol.Name[0] == 'a') {
161              byte bitPos;
162              if (byte.TryParse(node.Symbol.Name.Substring(1), out bitPos)) {
163                return bs.Select(b => GetBits(b, bitPos));
164              }
165            } else if (node.Symbol.Name[0] == 'd') {
166              byte bitPos;
167              if (byte.TryParse(node.Symbol.Name.Substring(1), out bitPos)) {
168                return bs.Select(b => GetBits(b, (byte)(bitPos + addrBits))); // offset of input line bits
169              }
170            }
171
172            throw new NotSupportedException(string.Format("Found unexpected symbol {0}", node.Symbol.Name));
173          }
174      }
175    }
176
177    private static IEnumerable<bool> EvalIf(ISymbolicExpressionTreeNode pred, ISymbolicExpressionTreeNode trueBranch, ISymbolicExpressionTreeNode falseBranch, IEnumerable<int> bs, byte addrBits) {
178      var preds = InterpretRec(pred, bs, addrBits).GetEnumerator();
179      var tB = InterpretRec(trueBranch, bs, addrBits).GetEnumerator();
180      var fB = InterpretRec(falseBranch, bs, addrBits).GetEnumerator();
181      // start enumerators
182
183      while (preds.MoveNext() & tB.MoveNext() & fB.MoveNext()) {
184        if (preds.Current) yield return tB.Current;
185        else yield return fB.Current;
186      }
187    }
188
189    private static bool GetBits(int b, byte bitPos) {
190      return (b & (1 << bitPos)) != 0;
191    }
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.