source: branches/2521_ProblemRefactoring/HeuristicLab.Problems.GeneticProgramming/3.3/Boolean/MultiplexerProblem.cs @ 17270

Last change on this file since 17270 was 17270, checked in by abeham, 3 years ago

#2521: worked on removing virtual from Maximization for single-objective problems

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