#region License Information /* HeuristicLab * Copyright (C) 2002-2019 Heuristic and Evolutionary Algorithms Laboratory (HEAL) * * This file is part of HeuristicLab. * * HeuristicLab is free software: you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation, either version 3 of the License, or * (at your option) any later version. * * HeuristicLab is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with HeuristicLab. If not, see . */ #endregion using System; using System.Collections.Generic; using System.Diagnostics.Contracts; using System.Linq; using HEAL.Attic; using HeuristicLab.Common; using HeuristicLab.Core; using HeuristicLab.Data; using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding; using HeuristicLab.Parameters; namespace HeuristicLab.Problems.GeneticProgramming.Boolean { [Item("Multiplexer Problem (MUX)", "The Boolean multiplexer genetic programming problem. See Koza 1992, page 171, section 7.4.1 11-multiplexer.")] [Creatable(CreatableAttribute.Categories.GeneticProgrammingProblems, Priority = 900)] [StorableType("6DFE64E4-3968-446F-AE3D-FAF13C18930C")] public sealed class MultiplexerProblem : SymbolicExpressionTreeProblem { #region parameter names private const string NumberOfBitsParameterName = "NumberOfBits"; #endregion #region Parameter Properties public IFixedValueParameter NumberOfBitsParameter { get { return (IFixedValueParameter)Parameters[NumberOfBitsParameterName]; } } #endregion #region Properties public int NumberOfBits { get { return NumberOfBitsParameter.Value.Value; } set { NumberOfBitsParameter.Value.Value = value; } } #endregion public override bool Maximization { get { return true; } } #region item cloning and persistence // persistence [StorableConstructor] private MultiplexerProblem(StorableConstructorFlag _) : base(_) { } [StorableHook(HookType.AfterDeserialization)] private void AfterDeserialization() { RegisterEventHandlers(); } // cloning private MultiplexerProblem(MultiplexerProblem original, Cloner cloner) : base(original, cloner) { RegisterEventHandlers(); } public override IDeepCloneable Clone(Cloner cloner) { return new MultiplexerProblem(this, cloner); } #endregion public MultiplexerProblem() : base() { Parameters.Add(new FixedValueParameter(NumberOfBitsParameterName, "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", new IntValue(11))); var g = new SimpleSymbolicExpressionGrammar(); // will be replaced in update grammar Encoding = new SymbolicExpressionTreeEncoding(g, 100, 17); Encoding.GrammarParameter.ReadOnly = true; UpdateGrammar(); RegisterEventHandlers(); } private void UpdateGrammar() { var g = new SimpleSymbolicExpressionGrammar(); g.AddSymbols(new[] { "AND", "OR" }, 2, 2); // See Koza 1992, page 171, section 7.4.1 11-multiplexer g.AddSymbols(new[] { "NOT" }, 1, 1); g.AddSymbols(new[] { "IF" }, 3, 3); // find the number of address lines and input lines // e.g. 11-MUX: 3 addrBits + 8 input bits var addrBits = (int)Math.Log(NumberOfBits, 2); // largest power of two that fits into the number of bits var inputBits = NumberOfBits - addrBits; for (int i = 0; i < addrBits; i++) g.AddTerminalSymbol(string.Format("a{0}", i)); for (int i = 0; i < inputBits; i++) g.AddTerminalSymbol(string.Format("d{0}", i)); Encoding.GrammarParameter.ReadOnly = false; Encoding.Grammar = g; Encoding.GrammarParameter.ReadOnly = true; BestKnownQuality = Math.Pow(2, NumberOfBits); // this is a benchmark problem (the best achievable quality is known for a given number of bits) } public override double Evaluate(ISymbolicExpressionTree tree, IRandom random) { if (NumberOfBits <= 0) throw new NotSupportedException("Number of bits must be larger than zero."); if (NumberOfBits > 37) throw new NotSupportedException("Multiplexer does not support problems with number of bits > 37."); var bs = Enumerable.Range(0, (int)Math.Pow(2, NumberOfBits)); var addrBits = (int)Math.Log(NumberOfBits, 2); // largest power of two that fits into the number of bits var inputBits = NumberOfBits - addrBits; var targets = bs.Select(b => CalcTarget(b, addrBits, inputBits)); var pred = Interpret(tree, bs, (byte)addrBits); return targets.Zip(pred, (t, p) => t == p ? 1 : 0).Sum(); // count number of correct predictions } private bool CalcTarget(int b, int addrBits, int inputBits) { Contract.Assert(addrBits > 0); // calc addr int addr = 0; for (int i = addrBits - 1; i >= 0; i--) { addr = addr << 1; if (GetBits(b, (byte)i)) addr += 1; } if (addr <= inputBits) return GetBits(b, (byte)(addrBits + addr)); else return false; // in case the number of bits is smaller then necessary we assume that the remaining lines are false } private static IEnumerable Interpret(ISymbolicExpressionTree tree, IEnumerable bs, byte addrBits) { // skip programRoot and startSymbol return InterpretRec(tree.Root.GetSubtree(0).GetSubtree(0), bs, addrBits); } private static IEnumerable InterpretRec(ISymbolicExpressionTreeNode node, IEnumerable bs, byte addrBits) { Func, IEnumerable> unaryEval = (child, f) => InterpretRec(child, bs, addrBits).Select(f); Func, IEnumerable> binaryEval = (left, right, f) => InterpretRec(left, bs, addrBits).Zip(InterpretRec(right, bs, addrBits), f); switch (node.Symbol.Name) { case "AND": return binaryEval(node.GetSubtree(0), node.GetSubtree(1), (x, y) => x & y); case "OR": return binaryEval(node.GetSubtree(0), node.GetSubtree(1), (x, y) => x | y); case "NOT": return unaryEval(node.GetSubtree(0), (x) => !x); case "IF": return EvalIf(node.GetSubtree(0), node.GetSubtree(1), node.GetSubtree(2), bs, addrBits); default: { if (node.Symbol.Name[0] == 'a') { byte bitPos; if (byte.TryParse(node.Symbol.Name.Substring(1), out bitPos)) { return bs.Select(b => GetBits(b, bitPos)); } } else if (node.Symbol.Name[0] == 'd') { byte bitPos; if (byte.TryParse(node.Symbol.Name.Substring(1), out bitPos)) { return bs.Select(b => GetBits(b, (byte)(bitPos + addrBits))); // offset of input line bits } } throw new NotSupportedException(string.Format("Found unexpected symbol {0}", node.Symbol.Name)); } } } private static IEnumerable EvalIf(ISymbolicExpressionTreeNode pred, ISymbolicExpressionTreeNode trueBranch, ISymbolicExpressionTreeNode falseBranch, IEnumerable bs, byte addrBits) { var preds = InterpretRec(pred, bs, addrBits).GetEnumerator(); var tB = InterpretRec(trueBranch, bs, addrBits).GetEnumerator(); var fB = InterpretRec(falseBranch, bs, addrBits).GetEnumerator(); // start enumerators while (preds.MoveNext() & tB.MoveNext() & fB.MoveNext()) { if (preds.Current) yield return tB.Current; else yield return fB.Current; } } private static bool GetBits(int b, byte bitPos) { return (b & (1 << bitPos)) != 0; } #region events private void RegisterEventHandlers() { NumberOfBitsParameter.Value.ValueChanged += (sender, args) => UpdateGrammar(); } #endregion } }