1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022016 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  using System;


22  using System.Collections.Generic;


23  using System.Diagnostics.Contracts;


24  using System.Linq;


25 


26  namespace HeuristicLab.Algorithms.DataAnalysis.MctsSymbolicRegression {


27  internal enum UnaryFunctionType { Log, Exp, Inv };


28  internal interface Factor { }


29  internal class SymbolFactor : Factor {


30  internal char symbolId;


31  public SymbolFactor(char symbolId) {


32  this.symbolId = symbolId;


33  }


34  public override int GetHashCode() {


35  return symbolId.GetHashCode();


36  }


37  public override bool Equals(object obj) {


38  SymbolFactor other = obj as SymbolFactor;


39  if (other == null) return false;


40  else return other.symbolId == this.symbolId;


41  }


42  }


43  internal class FunctionFactor : Factor {


44  internal UnaryFunctionType functionType;


45  internal Polynomial argument;


46 


47  public FunctionFactor(UnaryFunctionType functionType, Polynomial argument) {


48  this.functionType = functionType;


49  this.argument = argument;


50  }


51 


52  public override int GetHashCode() {


53  var h = functionType.GetHashCode();


54  return ((h<<5)+h) ^ argument.GetHashCode();


55  }


56  public override bool Equals(object obj) {


57  FunctionFactor other = obj as FunctionFactor;


58  if (other == null) return false;


59  return


60  other.functionType == this.functionType &&


61  other.argument == this.argument;


62  }


63  }


64 


65  internal class Monomial {


66  internal List<Factor> factors = new List<Factor>();


67  public Monomial(params Factor[] factor) {


68  foreach (var f in factor) factors.Add(f);


69  }


70  public override int GetHashCode() {


71  return factors.OrderBy(ti => ti.GetHashCode()).Aggregate(0, (a, ti) => ((a << 5) + a) ^ ti.GetHashCode());


72  }


73  public override bool Equals(object obj) {


74  Monomial other = obj as Monomial;


75  if (other == null) return false;


76  if (other.factors.Count != this.factors.Count) return false;


77  return factors.All(ti => other.factors.Contains(ti)) &&


78  other.factors.All(ti => factors.Contains(ti));


79  }


80 


81  public static Monomial Product(Monomial a, Monomial b) {


82  var p = new Monomial();


83  var invFactorArg = new Polynomial();


84  var expFactorArg = new Polynomial();


85  var expFactor = new FunctionFactor(UnaryFunctionType.Exp, expFactorArg);


86 


87  foreach (var aFactor in a.factors.Concat(b.factors)) {


88  // collect all exp and inv factors into one and simplify


89  var funcFactor = aFactor as FunctionFactor;


90  if (funcFactor != null && funcFactor.functionType == UnaryFunctionType.Exp) {


91  expFactorArg.Add(funcFactor.argument);


92  } else if (funcFactor != null && funcFactor.functionType == UnaryFunctionType.Inv) {


93  if (!invFactorArg.terms.Any()) invFactorArg.terms = new HashSet<Monomial>(funcFactor.argument.terms);


94  else invFactorArg.Mul(funcFactor.argument);


95  } else {


96  p.factors.Add(aFactor);


97  }


98  }


99  if (expFactorArg.terms.Any()) {


100  p.factors.Add(expFactor);


101  }


102  if (invFactorArg.terms.Any()) {


103  var invFactor = new FunctionFactor(UnaryFunctionType.Inv, invFactorArg);


104  p.factors.Add(invFactor);


105  }


106  return p;


107  }


108  }


109 


110  internal class Polynomial {


111  internal HashSet<Monomial> terms = new HashSet<Monomial>();


112  public Polynomial(params Monomial[] term) {


113  foreach (var t in term) terms.Add(t);


114  }


115  public void Add(Polynomial other) {


116  this.terms.UnionWith(other.terms);


117  }


118  public void Mul(Polynomial other) {


119  var myTerms = terms;


120  var otherTerms = other.terms;


121  var newTerms = new HashSet<Monomial>();


122  foreach (var a in myTerms) {


123  foreach (var b in otherTerms) {


124  newTerms.Add(Monomial.Product(a, b));


125  }


126  }


127  terms = newTerms;


128  }


129  public override int GetHashCode() {


130  return terms.OrderBy(ti => ti.GetHashCode()).Aggregate(0, (a, ti) => ((a<<5)+a) ^ ti.GetHashCode());


131  }


132  public override bool Equals(object obj) {


133  Polynomial other = obj as Polynomial;


134  if (other == null) return false;


135  if (other.terms.Count != this.terms.Count) return false;


136  return terms.All(ti => other.terms.Contains(ti)) &&


137  other.terms.All(ti => terms.Contains(ti));


138  }


139  }


140 


141 


142  // calculates a hashcode for expressions.


143 


144  public static class ExprHashSymbolic {


145 


146 


147  const int MaxStackSize = 100;


148  const int MaxVariables = 26;


149  private static SymbolFactor[] varSymbols;


150  private static SymbolFactor zero;


151  private static SymbolFactor one;


152 


153 


154  static ExprHashSymbolic() {


155  const string symbols = "abcdefghijklmnopqrstuvwxyz";


156 


157  varSymbols = new SymbolFactor[MaxVariables];


158  for (int i = 0; i < MaxVariables; i++) {


159  varSymbols[i] = new SymbolFactor(symbols[i]);


160  }


161  zero = new SymbolFactor('0');


162  one = new SymbolFactor('1');


163  }


164 


165  public static int GetHash(byte[] code, int nParams) {


166  return Eval(code, nParams);


167  }


168 


169  private static int Eval(byte[] code, int nParams) {


170  // The hash code calculation already preserves commutativity, associativity and distributivity of operations.


171  // We assume that the structure contains numeric parameters


172  // x = c*x


173  // exp(x) = c*exp(c*x)


174  // log(x) = c*log(x+c)


175  // inv(x) = c/(x+c)


176  // Accordingly, each structure represents a class of functions.


177 


178  // The following expressions should hash to the same value as they represent


179  // equivalent function classes


180  //  x1 + x1 is equivalent to x1


181  //  exp(x1) * exp(x1) is equivalent to exp(x1)


182  //


183  // The following experssions must not hash to the same value.


184  //  exp(x1) + exp(x1) is different from exp(x1)


185  //  log(x1) + log(x1) is different from log(x1)


186  //  1/x1 + 1/x1 is different from 1/x1


187  //  TODO list all


188 


189  // think about speed later (TODO)


190 


191  var stack = new Polynomial[MaxStackSize];


192  int topOfStack = 1;


193  int pc = 0;


194  int nextParamIdx = 1;


195  OpCodes op;


196  short arg;


197  while (true) {


198  ReadNext(code, ref pc, out op, out arg);


199  switch (op) {


200  case OpCodes.Nop: break;


201  case OpCodes.LoadConst0: {


202  ++topOfStack;


203  stack[topOfStack] = new Polynomial(new Monomial(zero));


204  break;


205  }


206  case OpCodes.LoadConst1: {


207  ++topOfStack;


208  stack[topOfStack] = new Polynomial(new Monomial(one));


209  break;


210  }


211  case OpCodes.LoadParamN: {


212  ++topOfStack;


213  stack[topOfStack] = new Polynomial(new Monomial(one)); // TODO empty, or unique?


214  break;


215  }


216  case OpCodes.LoadVar: {


217  ++topOfStack;


218  stack[topOfStack] = new Polynomial(new Monomial(varSymbols[arg]));


219 


220  break;


221  }


222  case OpCodes.Add: {


223  stack[topOfStack  1].Add(stack[topOfStack]);


224  topOfStack;


225  break;


226  }


227  case OpCodes.Mul: {


228  stack[topOfStack  1].Mul(stack[topOfStack]);


229  topOfStack;


230  break;


231  }


232  case OpCodes.Log: {


233  var v1 = stack[topOfStack];


234  stack[topOfStack] = new Polynomial(new Monomial(new FunctionFactor(UnaryFunctionType.Log, v1)));


235  break;


236  }


237  case OpCodes.Exp: {


238  var v1 = stack[topOfStack];


239  stack[topOfStack] = new Polynomial(new Monomial(new FunctionFactor(UnaryFunctionType.Exp, v1)));


240  break;


241  }


242  case OpCodes.Inv: {


243  var v1 = stack[topOfStack];


244  stack[topOfStack] = new Polynomial(new Monomial(new FunctionFactor(UnaryFunctionType.Inv, v1)));


245  break;


246  }


247  case OpCodes.Exit:


248  Contract.Assert(topOfStack == 0);


249  return stack[topOfStack].GetHashCode();


250  default: throw new InvalidOperationException();


251  }


252  }


253  }


254 


255  private static void EvalTerms(HashSet<double> terms, double[] stack, ref int topOfStack) {


256  ++topOfStack;


257  stack[topOfStack] = terms.Sum();


258  terms.Clear();


259  }


260 


261  private static void ReadNext(byte[] code, ref int pc, out OpCodes op, out short s) {


262  op = (OpCodes)Enum.ToObject(typeof(OpCodes), code[pc++]);


263  s = 0;


264  if (op == OpCodes.LoadVar) {


265  s = (short)((code[pc] << 8)  code[pc + 1]);


266  pc += 2;


267  }


268  }


269  }


270  }

