Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.GP.StructureIdentification.Networks/3.2/NetworkToFunctionTransformer.cs @ 3016

Last change on this file since 3016 was 2674, checked in by gkronber, 15 years ago

Added weights for open parameters. #833 (Genetic Programming based search for equations (modeling with multiple target variables))

File size: 18.9 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2008 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.Linq;
25using System.Text;
26using HeuristicLab.Core;
27using HeuristicLab.Data;
28using HeuristicLab.GP.Interfaces;
29using HeuristicLab.Modeling;
30using HeuristicLab.DataAnalysis;
31using System.Diagnostics;
32using HeuristicLab.Common;
33
34namespace HeuristicLab.GP.StructureIdentification.Networks {
35  public class NetworkToFunctionTransformer : OperatorBase {
36    public NetworkToFunctionTransformer()
37      : base() {
38      AddVariableInfo(new VariableInfo("Network", "The network (open expression)", typeof(IGeneticProgrammingModel), VariableKind.In));
39      AddVariableInfo(new VariableInfo("TargetVariables", "Name of the target variables", typeof(ItemList<StringData>), VariableKind.In));
40      AddVariableInfo(new VariableInfo("FunctionTree", "The function tree with all targetvaribales", typeof(IGeneticProgrammingModel), VariableKind.New));
41    }
42
43    public override string Description {
44      get { return "Extracts the network (function tree with unbound parameters) and creates a closed form function tree for each target variable."; }
45    }
46
47    public override IOperation Apply(IScope scope) {
48      IGeneticProgrammingModel model = GetVariableValue<IGeneticProgrammingModel>("Network", scope, true);
49      ItemList<StringData> targetVariables = GetVariableValue<ItemList<StringData>>("TargetVariables", scope, true);
50      // clear old sub-scopes
51      while (scope.SubScopes.Count > 0) scope.RemoveSubScope(scope.SubScopes[0]);
52
53      var targetVariableEnumerator = targetVariables.Select(x => x.Data).GetEnumerator();
54      List<IFunctionTree> transformedTrees = new List<IFunctionTree>(Transform(model.FunctionTree, targetVariables.Select(x => x.Data)));
55      // create a new sub-scope for each target variable with the transformed expression
56      foreach (IFunctionTree transformedTree in transformedTrees) {
57        targetVariableEnumerator.MoveNext();
58        Scope exprScope = new Scope();
59        scope.AddSubScope(exprScope);
60        exprScope.AddVariable(new HeuristicLab.Core.Variable(scope.TranslateName("FunctionTree"), new GeneticProgrammingModel(transformedTree)));
61        exprScope.AddVariable(new HeuristicLab.Core.Variable(scope.TranslateName("TargetVariable"), new StringData(targetVariableEnumerator.Current)));
62        Debug.Assert(!(transformedTree is VariableFunctionTree) || ((VariableFunctionTree)transformedTree).VariableName != targetVariableEnumerator.Current);
63      }
64
65      return null;
66    }
67
68    private static IEnumerable<IFunctionTree> Transform(IFunctionTree networkDescription, IEnumerable<string> targetVariables) {
69      // bind open parameters of network to target variables
70      //IFunctionTree openExpression = RemoveOpenParameters(networkDescription);
71      IFunctionTree paritallyEvaluatedOpenExpression = ApplyMetaFunctions((IFunctionTree)networkDescription.Clone());
72      IFunctionTree boundExpression = BindVariables(paritallyEvaluatedOpenExpression, targetVariables.GetEnumerator());
73
74      // create a new sub-scope for each target variable with the transformed expression
75      foreach (var targetVariable in targetVariables) {
76        yield return TransformExpression((IFunctionTree)boundExpression.Clone(), targetVariable, targetVariables.Except(new string[] { targetVariable }));
77      }
78    }
79
80    /// <summary>
81    /// applies all tree-transforming meta functions (= cycle and flip)
82    /// precondition: root is a F2 function (possibly cycle) and the tree contains 0 or n flip functions, each branch has an openparameter symbol in the bottom left
83    /// postconditon: root is any F2 function (but cycle) and the tree doesn't contains any flips, each branch has an openparameter symbol in the bottom left
84    /// </summary>
85    /// <param name="tree"></param>
86    /// <returns></returns>
87    private static IFunctionTree ApplyMetaFunctions(IFunctionTree tree) {
88      return ApplyFlips(ApplyCycles(tree));
89    }
90
91    private static IFunctionTree ApplyFlips(IFunctionTree tree) {
92      if (tree.SubTrees.Count == 0) {
93        return tree;
94      } else if (tree.Function is Flip) {
95        var partiallyAppliedBranch = ApplyFlips(tree.SubTrees[0]);
96        if (partiallyAppliedBranch.Function is OpenParameter) {
97          var openParFunTree = (OpenParameterFunctionTree)partiallyAppliedBranch;
98          openParFunTree.Weight = 1.0 / openParFunTree.Weight;
99          return partiallyAppliedBranch;
100        } else return InvertChain(partiallyAppliedBranch);
101      } else {
102        List<IFunctionTree> subTrees = new List<IFunctionTree>(tree.SubTrees);
103        while (tree.SubTrees.Count > 0) tree.RemoveSubTree(0);
104        foreach (var subTree in subTrees) {
105          tree.AddSubTree(ApplyFlips(subTree));
106        }
107        return tree;
108      }
109    }
110
111    /// <summary>
112    ///  inverts and reverses chain of functions.
113    ///  precondition: tree is any F1 non-terminal that ends with an openParameter
114    ///  postcondition: tree is inverted and reversed chain of F1 non-terminals and ends with an openparameter.
115    /// </summary>
116    /// <param name="tree"></param>
117    /// <returns></returns>
118    private static IFunctionTree InvertChain(IFunctionTree tree) {
119      List<IFunctionTree> currentChain = new List<IFunctionTree>(IterateChain(tree));
120      // get a list of function trees from bottom to top
121      List<IFunctionTree> reversedChain = new List<IFunctionTree>(currentChain.Reverse<IFunctionTree>().Skip(1));
122      OpenParameterFunctionTree openParam = (OpenParameterFunctionTree)currentChain.Last();
123
124      // build new tree by inverting every function in the reversed chain and keeping f0 branches untouched.
125      IFunctionTree parent = reversedChain[0];
126      IFunctionTree invParent = GetInvertedFunction(parent.Function).GetTreeNode();
127      for (int j = 1; j < parent.SubTrees.Count; j++) {
128        invParent.AddSubTree(parent.SubTrees[j]);
129      }
130      IFunctionTree root = invParent;
131      for (int i = 1; i < reversedChain.Count(); i++) {
132        IFunctionTree child = reversedChain[i];
133        IFunctionTree invChild = GetInvertedFunction(child.Function).GetTreeNode();
134        invParent.InsertSubTree(0, invChild);
135
136        parent = child;
137        invParent = invChild;
138        for (int j = 1; j < parent.SubTrees.Count; j++) {
139          invParent.AddSubTree(parent.SubTrees[j]);
140        }
141      }
142      // invert factor of openParam
143      openParam.Weight = 1.0 / openParam.Weight;
144      // append open param at the end
145      invParent.InsertSubTree(0, openParam);
146      return root;
147    }
148
149    private static IEnumerable<IFunctionTree> IterateChain(IFunctionTree tree) {
150      while (tree.SubTrees.Count > 0) {
151        yield return tree;
152        tree = tree.SubTrees[0];
153      }
154      yield return tree;
155    }
156
157
158    private static Dictionary<Type, IFunction> invertedFunction = new Dictionary<Type, IFunction>() {
159      { typeof(AdditionF1), new SubtractionF1() },
160      { typeof(SubtractionF1), new AdditionF1() },
161      { typeof(MultiplicationF1), new DivisionF1() },
162      { typeof(DivisionF1), new MultiplicationF1() },
163      { typeof(OpenLog), new OpenExp() },
164      { typeof(OpenExp), new OpenLog() },
165      //{ typeof(OpenSqr), new OpenSqrt() },
166      //{ typeof(OpenSqrt), new OpenSqr() },
167      { typeof(Flip), new Flip()},
168      { typeof(Addition), new Subtraction()},
169      { typeof(Subtraction), new Addition()},
170      { typeof(Multiplication), new Division()},
171      { typeof(Division), new Multiplication()},
172      { typeof(Exponential), new Logarithm()},
173      { typeof(Logarithm), new Exponential()}
174    };
175    private static IFunction GetInvertedFunction(IFunction function) {
176      return invertedFunction[function.GetType()];
177    }
178
179    private static IFunctionTree ApplyCycles(IFunctionTree tree) {
180      int nRotations = 0;
181      while (tree.Function is Cycle) {
182        nRotations++;
183        tree = tree.SubTrees[0];
184      }
185      if (nRotations > 0 && nRotations % tree.SubTrees.Count > 0) {
186        IFunctionTree[] subTrees = tree.SubTrees.ToArray();
187        while (tree.SubTrees.Count > 0) tree.RemoveSubTree(0);
188
189        nRotations = nRotations % subTrees.Length;
190        Array.Reverse(subTrees, 0, nRotations);
191        Array.Reverse(subTrees, nRotations, subTrees.Length - nRotations);
192        Array.Reverse(subTrees, 0, subTrees.Length);
193
194        for (int i = 0; i < subTrees.Length; i++) {
195          tree.AddSubTree(subTrees[i]);
196        }
197      }
198      return tree;
199    }
200
201
202
203    //private static IFunctionTree AppendLeft(IFunctionTree tree, IFunctionTree node) {
204    //  IFunctionTree originalTree = tree;
205    //  while (!IsBottomLeft(tree)) tree = tree.SubTrees[0];
206    //  tree.InsertSubTree(0, node);
207    //  return originalTree;
208    //}
209
210    private static bool IsBottomLeft(IFunctionTree tree) {
211      if (tree.SubTrees.Count == 0) return true;
212      else if (tree.SubTrees[0].Function is Variable) return true;
213      else if (tree.SubTrees[0].Function is Constant) return true;
214      else return false;
215    }
216
217    /// <summary>
218    /// recieves a function tree transforms it into a function-tree for the given target variable
219    /// </summary>
220    /// <param name="tree"></param>
221    /// <param name="targetVariable"></param>
222    /// <returns></returns>
223    private static IFunctionTree TransformExpression(IFunctionTree tree, string targetVariable, IEnumerable<string> parameters) {
224      if (tree.Function is Constant) return tree;
225      if (tree.Function is Variable || tree.Function is Differential) {
226        VariableFunctionTree varTree = (VariableFunctionTree)tree;
227        varTree.Weight = 1.0;
228        if (varTree.VariableName == targetVariable) varTree.VariableName = parameters.First();
229        return varTree;
230      }
231      if (tree.Function is Addition || tree.Function is Subtraction ||
232          tree.Function is Multiplication || tree.Function is Division ||
233          tree.Function is Exponential || tree.Function is Logarithm) {
234        var occuringVariables = from x in FunctionTreeIterator.IteratePrefix(tree)
235                                where x is VariableFunctionTree
236                                let name = ((VariableFunctionTree)x).VariableName
237                                select name;
238        var openParameters = (new string[] { targetVariable }).Concat(parameters);
239        var missingVariables = openParameters.Except(occuringVariables);
240        if (missingVariables.Count() > 0) {
241          VariableFunctionTree varTree = (VariableFunctionTree)(new Variable()).GetTreeNode();
242          varTree.VariableName = missingVariables.First();
243          varTree.SampleOffset = 0;
244          varTree.Weight = 1.0;
245          tree = (IFunctionTree)tree.Clone();
246          tree.InsertSubTree(0, varTree);
247        }
248      }
249      int targetIndex = -1;
250      IFunctionTree combinator = null;
251      List<IFunctionTree> subTrees = new List<IFunctionTree>(tree.SubTrees);
252      if (HasTargetVariable(subTrees[0], targetVariable)) {
253        targetIndex = 0;
254        combinator = FunctionFromCombinator(tree).GetTreeNode();
255      } else {
256        for (int i = 1; i < subTrees.Count; i++) {
257          if (HasTargetVariable(subTrees[i], targetVariable)) {
258            targetIndex = i;
259            combinator = GetInvertedFunction(FunctionFromCombinator(tree)).GetTreeNode();
260            break;
261          }
262        }
263      }
264      if (targetIndex == -1) {
265        // target variable was not found
266        return tree;
267      } else {
268        // target variable was found
269        for (int i = 0; i < subTrees.Count; i++) {
270          if (i != targetIndex)
271            combinator.AddSubTree(subTrees[i]);
272        }
273        if (subTrees[targetIndex].Function is Variable) return MakeMultiplication(combinator, 1.0 / GetTargetVariableWeight(subTrees[targetIndex]));
274        else {
275          IFunctionTree bottomLeft;
276          IFunctionTree targetChain = InvertF0Chain(subTrees[targetIndex], out bottomLeft);
277          bottomLeft.InsertSubTree(0, combinator);
278          return MakeMultiplication(targetChain, 1.0 / GetTargetVariableWeight(subTrees[targetIndex]));
279        }
280      }
281    }
282
283    private static IFunctionTree MakeMultiplication(IFunctionTree tree, double p) {
284      if (p.IsAlmost(1.0)) return tree;
285      var mul = (new Multiplication()).GetTreeNode();
286      var constP = (ConstantFunctionTree)(new Constant()).GetTreeNode();
287      constP.Value = p;
288      mul.AddSubTree(tree);
289      mul.AddSubTree(constP);
290      return mul;
291    }
292
293    private static double GetTargetVariableWeight(IFunctionTree tree) {
294      while (tree.SubTrees.Count > 0) {
295        tree = tree.SubTrees[0];
296      }
297      return ((VariableFunctionTree)tree).Weight;
298    }
299
300    // inverts a chain of F0 functions
301    // precondition: left bottom is a variable (the selected target variable)
302    // postcondition: the chain is inverted. the target variable is removed
303    private static IFunctionTree InvertF0Chain(IFunctionTree tree, out IFunctionTree bottomLeft) {
304      List<IFunctionTree> currentChain = IterateChain(tree).ToList();
305
306      List<IFunctionTree> reversedChain = currentChain.Reverse<IFunctionTree>().Skip(1).ToList();
307
308      // build new tree by inverting every function in the reversed chain and keeping f0 branches untouched.
309      IFunctionTree parent = reversedChain[0];
310      IFunctionTree invParent = GetInvertedFunction(parent.Function).GetTreeNode();
311      for (int j = 1; j < parent.SubTrees.Count; j++) {
312        invParent.AddSubTree(parent.SubTrees[j]);
313      }
314      IFunctionTree root = invParent;
315      for (int i = 1; i < reversedChain.Count(); i++) {
316        IFunctionTree child = reversedChain[i];
317        IFunctionTree invChild = GetInvertedFunction(child.Function).GetTreeNode();
318        invParent.InsertSubTree(0, invChild);
319        parent = child;
320        invParent = invChild;
321        for (int j = 1; j < parent.SubTrees.Count; j++) {
322          invParent.AddSubTree(parent.SubTrees[j]);
323        }
324      }
325      bottomLeft = invParent;
326      return root;
327    }
328
329
330
331    //private static IFunctionTree InvertCombinator(IFunctionTree tree) {
332    //  if (tree.Function is OpenAddition) {
333    //    return (new OpenSubtraction()).GetTreeNode();
334    //  } else if (tree.Function is OpenSubtraction) {
335    //    return (new OpenAddition()).GetTreeNode();
336    //  } else if (tree.Function is OpenMultiplication) {
337    //    return (new OpenDivision()).GetTreeNode();
338    //  } else if (tree.Function is OpenDivision) {
339    //    return (new OpenMultiplication()).GetTreeNode();
340    //  } else throw new InvalidOperationException();
341    //}
342
343    private static Dictionary<Type, IFunction> combinatorFunction = new Dictionary<Type, IFunction>() {
344      { typeof(OpenAddition), new Addition()},
345      { typeof(OpenSubtraction), new Subtraction()},
346      { typeof(OpenDivision), new Division()},
347      { typeof(OpenMultiplication), new Multiplication()},
348      { typeof(Addition), new Addition()},
349      { typeof(Subtraction), new Subtraction()},
350      { typeof(Division), new Division()},
351      { typeof(Multiplication), new Multiplication()},
352      { typeof(Logarithm), new Logarithm()},
353      { typeof(Exponential), new Exponential()},
354    };
355    private static IFunction FunctionFromCombinator(IFunctionTree tree) {
356      return combinatorFunction[tree.Function.GetType()];
357    }
358
359    private static bool HasTargetVariable(IFunctionTree tree, string targetVariable) {
360      if (tree.SubTrees.Count == 0) {
361        var varTree = tree as VariableFunctionTree;
362        if (varTree != null) return varTree.VariableName == targetVariable;
363        else return false;
364      } else return (from x in tree.SubTrees
365                     where HasTargetVariable(x, targetVariable)
366                     select true).Any();
367    }
368
369    private static Dictionary<Type, IFunction> closedForm = new Dictionary<Type, IFunction>() {
370      {typeof(OpenAddition), new OpenAddition()},
371      {typeof(OpenSubtraction), new OpenSubtraction()},
372      {typeof(OpenMultiplication), new OpenMultiplication()},
373      {typeof(OpenDivision), new OpenDivision()},
374      {typeof(AdditionF1), new Addition()},
375      {typeof(SubtractionF1), new Subtraction()},
376      {typeof(MultiplicationF1), new Multiplication()},
377      {typeof(DivisionF1), new Division()},
378      {typeof(OpenExp), new Exponential()},
379      {typeof(OpenLog), new Logarithm()},
380      //{typeof(OpenSqr), new Power()},
381      //{typeof(OpenSqrt), new Sqrt()},
382      {typeof(OpenParameter), new Variable()},
383    };
384
385    /// <summary>
386    /// transforms a tree that contains F2 and F1 functions into a tree composed of F2 and F0 functions.
387    /// precondition: the tree doesn't contains cycle or flip symbols. the tree has openparameters in the bottom left
388    /// postcondition: all F1 and functions are replaced by matching F0 functions
389    /// </summary>
390    /// <param name="tree"></param>
391    /// <param name="targetVariables"></param>
392    /// <returns></returns>
393    private static IFunctionTree BindVariables(IFunctionTree tree, IEnumerator<string> targetVariables) {
394      if (!closedForm.ContainsKey(tree.Function.GetType())) return tree;
395      IFunction matchingFunction = closedForm[tree.Function.GetType()];
396      IFunctionTree matchingTree = matchingFunction.GetTreeNode();
397      if (matchingFunction is Variable) {
398        targetVariables.MoveNext();
399        var varTreeNode = (VariableFunctionTree)matchingTree;
400        varTreeNode.VariableName = targetVariables.Current;
401        varTreeNode.SampleOffset = ((OpenParameterFunctionTree)tree).SampleOffset;
402        varTreeNode.Weight = ((OpenParameterFunctionTree)tree).Weight;
403        return varTreeNode;
404        //} else if (matchingFunction is Power) {
405        //  matchingTree.AddSubTree(BindVariables(tree.SubTrees[0], targetVariables));
406        //  var const2 = (ConstantFunctionTree)(new Constant()).GetTreeNode();
407        //  const2.Value = 2.0;
408        //  matchingTree.AddSubTree(const2);
409      } else {
410        foreach (IFunctionTree subTree in tree.SubTrees) {
411          matchingTree.AddSubTree(BindVariables(subTree, targetVariables));
412        }
413      }
414
415      return matchingTree;
416    }
417  }
418}
Note: See TracBrowser for help on using the repository browser.