Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Functions/BakedFunctionTree.cs @ 324

Last change on this file since 324 was 324, checked in by gkronber, 16 years ago

added Size and Height properties to interface IFunctionTree and removed the helper methods from TreeGardener (specific implementations of size and height properties in classes implementing IFunctionTree can be more efficient than the general functions in TreeGardener)

File size: 12.2 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.DataAnalysis;
28using HeuristicLab.Data;
29using System.Xml;
30using System.Globalization;
31
32namespace HeuristicLab.Functions {
33
34  class LightWeightFunction {
35    public int arity = 0;
36    public IFunction functionType;
37    public List<double> data = new List<double>();
38
39    public LightWeightFunction Clone() {
40      LightWeightFunction clone = new LightWeightFunction();
41      clone.arity = arity;
42      clone.functionType = functionType;
43      clone.data.AddRange(data);
44      return clone;
45    }
46  }
47
48  class BakedFunctionTree : ItemBase, IFunctionTree {
49    private List<LightWeightFunction> linearRepresentation;
50    private bool treesExpanded = false;
51    private List<IFunctionTree> subTrees;
52    private bool variablesExpanded = false;
53    private List<IVariable> variables;
54
55    public BakedFunctionTree() {
56      linearRepresentation = new List<LightWeightFunction>();
57    }
58
59    internal BakedFunctionTree(IFunction function)
60      : this() {
61      LightWeightFunction fun = new LightWeightFunction();
62      fun.functionType = function;
63      linearRepresentation.Add(fun);
64      treesExpanded = true;
65      subTrees = new List<IFunctionTree>();
66      variables = new List<IVariable>();
67      variablesExpanded = true;
68      foreach(IVariableInfo variableInfo in function.VariableInfos) {
69        if(variableInfo.Local) {
70          variables.Add((IVariable)function.GetVariable(variableInfo.FormalName).Clone());
71        }
72      }
73    }
74
75    internal BakedFunctionTree(IFunctionTree tree)
76      : this() {
77      LightWeightFunction fun = new LightWeightFunction();
78      fun.functionType = tree.Function;
79      linearRepresentation.Add(fun);
80      foreach(IVariable variable in tree.LocalVariables) {
81        IItem value = variable.Value;
82        fun.data.Add(GetDoubleValue(value));
83      }
84      foreach(IFunctionTree subTree in tree.SubTrees) {
85        AddSubTree(new BakedFunctionTree(subTree));
86      }
87    }
88
89    private double GetDoubleValue(IItem value) {
90      if(value is DoubleData) {
91        return ((DoubleData)value).Data;
92      } else if(value is ConstrainedDoubleData) {
93        return ((ConstrainedDoubleData)value).Data;
94      } else if(value is IntData) {
95        return ((IntData)value).Data;
96      } else if(value is ConstrainedIntData) {
97        return ((ConstrainedIntData)value).Data;
98      } else throw new NotSupportedException("Invalid datatype of local variable for GP");
99    }
100
101    private int BranchLength(int branchRoot) {
102      int arity = linearRepresentation[branchRoot].arity;
103      int length = 1;
104      for(int i = 0; i < arity; i++) {
105        length += BranchLength(branchRoot + length);
106      }
107      return length;
108    }
109
110    private void FlattenTrees() {
111      if(treesExpanded) {
112        linearRepresentation[0].arity = subTrees.Count;
113        foreach(BakedFunctionTree subTree in subTrees) {
114          subTree.FlattenVariables();
115          subTree.FlattenTrees();
116          linearRepresentation.AddRange(subTree.linearRepresentation);
117        }
118        treesExpanded = false;
119        subTrees = null;
120      }
121    }
122
123    private void FlattenVariables() {
124      if(variablesExpanded) {
125        linearRepresentation[0].data.Clear();
126        foreach(IVariable variable in variables) {
127          linearRepresentation[0].data.Add(GetDoubleValue(variable.Value));
128        }
129        variablesExpanded = false;
130        variables = null;
131      }
132    }
133
134    public int Size {
135      get {
136        if(treesExpanded) {
137          int size = 1;
138          foreach(BakedFunctionTree tree in subTrees) {
139            size += tree.Size;
140          }
141          return size;
142        } else
143        return linearRepresentation.Count;
144      }
145    }
146
147    public int Height {
148      get {
149        if(treesExpanded) {
150          int height = 0;
151          foreach(IFunctionTree subTree in subTrees) {
152            int curHeight = subTree.Height;
153            if(curHeight > height) height = curHeight;
154          }
155          return height+1;
156        } else {
157          int nextBranchStart;
158          return BranchHeight(0, out nextBranchStart);
159        }
160      }
161    }
162
163    private int BranchHeight(int branchStart, out int nextBranchStart) {
164      LightWeightFunction f = linearRepresentation[branchStart];
165      int height = 0;
166      branchStart++;
167      for(int i = 0; i < f.arity; i++) {
168        int curHeight = BranchHeight(branchStart, out nextBranchStart);
169        if(curHeight > height) height = curHeight;
170        branchStart = nextBranchStart;
171      }
172      nextBranchStart = branchStart;
173      return height + 1;
174    }
175
176    public IList<IFunctionTree> SubTrees {
177      get {
178        if(!treesExpanded) {
179          subTrees = new List<IFunctionTree>();
180          int arity = linearRepresentation[0].arity;
181          int branchIndex = 1;
182          for(int i = 0; i < arity; i++) {
183            BakedFunctionTree subTree = new BakedFunctionTree();
184            int length = BranchLength(branchIndex);
185            for(int j = branchIndex; j < branchIndex + length; j++) {
186              subTree.linearRepresentation.Add(linearRepresentation[j]);
187            }
188            branchIndex += length;
189            subTrees.Add(subTree);
190          }
191          treesExpanded = true;
192          linearRepresentation.RemoveRange(1, linearRepresentation.Count - 1);
193          linearRepresentation[0].arity = 0;
194        }
195        return subTrees;
196      }
197    }
198
199    public ICollection<IVariable> LocalVariables {
200      get {
201        if(!variablesExpanded) {
202          variables = new List<IVariable>();
203          IFunction function = Function;
204          int localVariableIndex = 0;
205          foreach(IVariableInfo variableInfo in function.VariableInfos) {
206            if(variableInfo.Local) {
207              IVariable clone = (IVariable)function.GetVariable(variableInfo.FormalName).Clone();
208              IItem value = clone.Value;
209              if(value is ConstrainedDoubleData) {
210                ((ConstrainedDoubleData)value).Data = linearRepresentation[0].data[localVariableIndex];
211              } else if(value is ConstrainedIntData) {
212                ((ConstrainedIntData)value).Data = (int)linearRepresentation[0].data[localVariableIndex];
213              } else if(value is DoubleData) {
214                ((DoubleData)value).Data = linearRepresentation[0].data[localVariableIndex];
215              } else if(value is IntData) {
216                ((IntData)value).Data = (int)linearRepresentation[0].data[localVariableIndex];
217              } else throw new NotSupportedException("Invalid local variable type for GP.");
218              variables.Add(clone);
219              localVariableIndex++;
220            }
221          }
222          variablesExpanded = true;
223          linearRepresentation[0].data.Clear();
224        }
225        return variables;
226      }
227    }
228
229    public IFunction Function {
230      get { return linearRepresentation[0].functionType; }
231    }
232
233    public IVariable GetLocalVariable(string name) {
234      foreach(IVariable var in LocalVariables) {
235        if(var.Name == name) return var;
236      }
237      return null;
238    }
239
240    public void AddVariable(IVariable variable) {
241      throw new NotSupportedException();
242    }
243
244    public void RemoveVariable(string name) {
245      throw new NotSupportedException();
246    }
247
248    public void AddSubTree(IFunctionTree tree) {
249      if(!treesExpanded) throw new InvalidOperationException();
250      subTrees.Add(tree);
251    }
252
253    public void InsertSubTree(int index, IFunctionTree tree) {
254      if(!treesExpanded) throw new InvalidOperationException();
255      subTrees.Insert(index, tree);
256    }
257
258    public void RemoveSubTree(int index) {
259      // sanity check
260      if(!treesExpanded) throw new InvalidOperationException();
261      subTrees.RemoveAt(index);
262    }
263
264    bool evaluatorReset = false;
265    public double Evaluate(Dataset dataset, int sampleIndex) {
266      FlattenVariables();
267      FlattenTrees();
268      if(!evaluatorReset) {
269        BakedTreeEvaluator.ResetEvaluator(linearRepresentation);
270        evaluatorReset = true;
271      }
272      return BakedTreeEvaluator.Evaluate(dataset, sampleIndex);
273    }
274
275
276    public override XmlNode GetXmlNode(string name, XmlDocument document, IDictionary<Guid, IStorable> persistedObjects) {
277      FlattenVariables();
278      FlattenTrees();
279      XmlNode node = base.GetXmlNode(name, document, persistedObjects);
280      XmlNode linearRepresentationNode = document.CreateElement("LinearRepresentation");
281      foreach(LightWeightFunction f in linearRepresentation) {
282        XmlNode entryNode = PersistenceManager.Persist("FunctionType", f.functionType, document, persistedObjects);
283        XmlAttribute arityAttribute = document.CreateAttribute("Arity");
284        arityAttribute.Value = f.arity+"";
285        entryNode.Attributes.Append(arityAttribute);
286        if(f.data.Count > 0) {
287          XmlAttribute dataAttribute = document.CreateAttribute("Data");
288          dataAttribute.Value = GetString<double>(f.data);
289          entryNode.Attributes.Append(dataAttribute);
290        }
291        linearRepresentationNode.AppendChild(entryNode);
292      }
293
294      node.AppendChild(linearRepresentationNode);
295      return node;
296    }
297
298    public override void Populate(XmlNode node, IDictionary<Guid, IStorable> restoredObjects) {
299      base.Populate(node, restoredObjects);
300      XmlNode linearRepresentationNode = node.SelectSingleNode("LinearRepresentation");
301      foreach(XmlNode entryNode in linearRepresentationNode.ChildNodes) {
302        LightWeightFunction f = new LightWeightFunction();
303        f.arity = int.Parse(entryNode.Attributes["Arity"].Value, CultureInfo.InvariantCulture);
304        if(entryNode.Attributes["Data"]!=null)
305          f.data = GetList<double>(entryNode.Attributes["Data"].Value, s => double.Parse(s, CultureInfo.InvariantCulture));
306        f.functionType = (IFunction)PersistenceManager.Restore(entryNode, restoredObjects);
307        linearRepresentation.Add(f);
308      }
309      treesExpanded = false;
310      variablesExpanded = false;
311    }
312
313    private string GetString<T>(IEnumerable<T> xs) where T : IConvertible {
314      StringBuilder builder = new StringBuilder();
315      foreach(T x in xs) {
316        builder.Append(x.ToString(CultureInfo.InvariantCulture) + "; ");
317      }
318      if(builder.Length > 0) builder.Remove(builder.Length - 2, 2);
319      return builder.ToString();
320    }
321
322    private List<T> GetList<T>(string s, Converter<string, T> converter) {
323      List<T> result = new List<T>();
324      string[] tokens = s.Split(new char[] { ';', ' ' }, StringSplitOptions.RemoveEmptyEntries);
325      foreach(string token in tokens) {
326        T x = converter(token.Trim());
327        result.Add(x);
328      }
329      return result;
330    }
331
332    public override object Clone(IDictionary<Guid, object> clonedObjects) {
333      BakedFunctionTree clone = new BakedFunctionTree();
334      // in case the user (de)serialized the tree between evaluation and selection we have to flatten the tree again.
335      if(treesExpanded) FlattenTrees();
336      if(variablesExpanded) FlattenVariables();
337      foreach(LightWeightFunction f in linearRepresentation) {
338        clone.linearRepresentation.Add(f.Clone());
339      }
340      return clone;
341    }
342
343    public override IView CreateView() {
344      return new FunctionTreeView(this);
345    }
346  }
347}
Note: See TracBrowser for help on using the repository browser.