Free cookie consent management tool by TermsFeed Policy Generator

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

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

Added test cases for network transformation and fixed bugs in network transformation operator. #833

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