Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 2631 was 2631, checked in by gkronber, 14 years ago

Fixed another problem in the operator for transformation of networks to closed-form function trees. #833 (Genetic Programming based search for equations (modeling with multiple target variables))

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