Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.GP/BakedFunctionTree.cs @ 1384

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

worked on #364 (Improve GP evaluation performance)

  • removed list of Instr
  • changes that didn't affect performance directly: reduced size of Instr class, added 'constant-folding' and pre-calculation of skip-lengths


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