Free cookie consent management tool by TermsFeed Policy Generator

Changeset 7792


Ignore:
Timestamp:
05/10/12 17:17:14 (13 years ago)
Author:
bburlacu
Message:

#1772: Changelog:

  • Removed GetCutIndex method, and corresponding index field in the GenealogyGraphNode.
  • Implemented tracking for mutated fragments.
  • Improved FindMatch method.
  • Added IterateNodesBreadth functionality to symbolic expression trees and nodes.
  • Added check conditions for clearing global tracking structures so that the 2 analyzers are not mutually exclusive anymore.
Location:
branches/HeuristicLab.EvolutionaryTracking
Files:
16 edited

Legend:

Unmodified
Added
Removed

  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Crossovers/TracingSymbolicExpressionTreeCrossover.cs

    r7788 r7792  
    2121
    2222using System;
     23using System.Collections.Generic;
    2324using System.Linq;
    2425using HeuristicLab.Common;
    … …  
    3536  /// A base class for operators that perform a crossover of symbolic expression trees.
    3637  /// </summary>
    37   [Item("SymbolicExpressionTreeCrossover",
    38     "A base class for operators that perform a crossover of symbolic expression trees.")]
     38  [Item("SymbolicExpressionTreeCrossover", "A base class for operators that perform a crossover of symbolic expression trees.")]
    3939  [StorableClass]
    4040  public abstract class TracingSymbolicExpressionTreeCrossover : SymbolicExpressionTreeOperator, ISymbolicExpressionTreeCrossover {
    … …  
    4646
    4747    #region Parameter Properties
    48 
    4948    public ILookupParameter<ItemArray<ISymbolicExpressionTree>> ParentsParameter {
    5049      get { return (ScopeTreeLookupParameter<ISymbolicExpressionTree>)Parameters[ParentsParameterName]; }
    5150    }
    52 
    5351    public ILookupParameter<ISymbolicExpressionTree> ChildParameter {
    5452      get { return (ILookupParameter<ISymbolicExpressionTree>)Parameters[ChildParameterName]; }
    5553    }
    56 
    5754    public LookupParameter<CloneMapType> GlobalCloneMapParameter {
    5855      get { return (LookupParameter<CloneMapType>)Parameters[GlobalCloneMapParameterName]; }
    5956    }
    60 
    6157    public LookupParameter<TraceMapType> GlobalTraceMapParameter {
    6258      get { return (LookupParameter<TraceMapType>)Parameters[GlobalTraceMapParameterName]; }
    6359    }
    64 
    6560    public LookupParameter<CloneMapType> GlobalFragmentMapParameter {
    6661      get { return (LookupParameter<CloneMapType>)Parameters[GlobalFragmentMapParameterName]; }
    6762    }
    68 
    6963    #endregion
    7064
    7165    #region Properties
    72 
    7366    public ItemArray<ISymbolicExpressionTree> Parents {
    7467      get { return ParentsParameter.ActualValue; }
    7568    }
    76 
    7769    public ISymbolicExpressionTree Child {
    7870      get { return ChildParameter.ActualValue; }
    7971      set { ChildParameter.ActualValue = value; }
    8072    }
    81 
    8273    public CloneMapType GlobalCloneMap {
    8374      get { return GlobalCloneMapParameter.ActualValue; }
    8475    }
    85 
     76    public TraceMapType GlobalTraceMap {
     77      get { return GlobalTraceMapParameter.ActualValue; }
     78    }
    8679    public CloneMapType GlobalFragmentMap {
    8780      get { return GlobalFragmentMapParameter.ActualValue; }
    8881    }
    89 
    90     public TraceMapType GlobalTraceMap {
    91       get { return GlobalTraceMapParameter.ActualValue; }
    92     }
    93 
    9482    #endregion
    9583
    … …  
    10593    protected TracingSymbolicExpressionTreeCrossover()
    10694      : base() {
    107       Parameters.Add(new ScopeTreeLookupParameter<ISymbolicExpressionTree>(ParentsParameterName,
    108                                                                            "The parent symbolic expression trees which should be crossed."));
    109       Parameters.Add(new LookupParameter<ISymbolicExpressionTree>(ChildParameterName,
    110                                                                   "The child symbolic expression tree resulting from the crossover."));
    111       Parameters.Add(new LookupParameter<CloneMapType>(GlobalCloneMapParameterName,
    112                                                        "A global map keeping track of trees and their clones (made during selection)."));
    113       Parameters.Add(new LookupParameter<CloneMapType>(GlobalFragmentMapParameterName,
    114                                                        "A global map keeping track of tree fragments received via crossover."));
    115       Parameters.Add(new LookupParameter<TraceMapType>(GlobalTraceMapParameterName,
    116                                                        "A global cache containing tracing info."));
     95      Parameters.Add(new ScopeTreeLookupParameter<ISymbolicExpressionTree>(ParentsParameterName, "The parent symbolic expression trees which should be crossed."));
     96      Parameters.Add(new LookupParameter<ISymbolicExpressionTree>(ChildParameterName, "The child symbolic expression tree resulting from the crossover."));
     97      Parameters.Add(new LookupParameter<CloneMapType>(GlobalCloneMapParameterName, "A global map keeping track of trees and their clones (made during selection)."));
     98      Parameters.Add(new LookupParameter<CloneMapType>(GlobalFragmentMapParameterName, "A global map keeping track of tree fragments received via crossover."));
     99      Parameters.Add(new LookupParameter<TraceMapType>(GlobalTraceMapParameterName, "A global cache containing tracing info."));
    117100    }
    118101
    … …  
    120103      if (Parents.Length != 2)
    121104        throw new ArgumentException("Number of parents must be exactly two for symbolic expression tree crossover operators.");
     105
    122106      // add global trace cache if not already present in global scope
    123107      var gScope = ExecutionContext.Scope;
    124       while (gScope.Parent != null) gScope = gScope.Parent;
     108      while (gScope.Parent != null)
     109        gScope = gScope.Parent;
    125110      if (GlobalTraceMap == null)
    126111        gScope.Variables.Add(new Variable(GlobalTraceMapParameterName, new TraceMapType()));
    127112      if (GlobalFragmentMap == null)
    128113        gScope.Variables.Add(new Variable(GlobalFragmentMapParameterName, new CloneMapType()));
    129       // get original parents
     114
     115      // get original parents (this info will be needed later to construct the genealogy graph)
    130116      var originalParents = new ItemList<IItem>(Parents.Select(x => GlobalCloneMap[x]));
     117
    131118      // save the nodes of parent0 in a list so we can track what modifications are made by crossover
    132       var nodes0 = Parents[0].IterateNodes().ToList();
     119      var nodes0 = Parents[0].IterateNodesBreadth() as List<ISymbolicExpressionTreeNode>;
     120
    133121      //perform crossover
    134122      Child = Crossover(Random, Parents[0], Parents[1]);
     123
    135124      // create another list of parent0's nodes, so we can compare it with the first list to see what changed
    136       var nodes1 = Child.IterateNodes().ToList();
     125      var nodes1 = Child.IterateNodesBreadth() as List<ISymbolicExpressionTreeNode>;
     126
    137127      // compare the two nodes lists and check the difference (comparing node references so we avoid false functional identity).
    138128      // if no difference is found, then it is assumed that the whole tree was swapped with itself (it can happen), so the index is 0
    … …  
    141131        if (nodes0[i] != nodes1[i]) break;
    142132      if (i == min) i = 0;
    143       GlobalTraceMap[Child] = originalParents;
    144       GlobalFragmentMap[Child] = new IntValue(i);
     133
     134      // add heredity information into the global variables
     135      GlobalTraceMap[Child] = originalParents; // map child to its corresponding parents from the previous generation
     136      GlobalFragmentMap[Child] = new IntValue(i); // map child to the index of its fragment
    145137      return base.Apply();
    146138    }

  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Interfaces/ISymbolicExpressionTree.cs

    r7439 r7792  
    3131    IEnumerable<ISymbolicExpressionTreeNode> IterateNodesPrefix();
    3232    IEnumerable<ISymbolicExpressionTreeNode> IterateNodesPostfix();
     33    IEnumerable<ISymbolicExpressionTreeNode> IterateNodesBreadth();
    3334  }
    3435}

  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Interfaces/ISymbolicExpressionTreeNode.cs

    r7522 r7792  
    3636    IEnumerable<ISymbolicExpressionTreeNode> IterateNodesPostfix();
    3737    IEnumerable<ISymbolicExpressionTreeNode> IterateNodesPrefix();
     38    IEnumerable<ISymbolicExpressionTreeNode> IterateNodesBreadth();
    3839    void ForEachNodePostfix(Action<ISymbolicExpressionTreeNode> a);
    3940    void ForEachNodePrefix(Action<ISymbolicExpressionTreeNode> a);

  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Manipulators/TracingSymbolicExpressionTreeManipulator.cs

    r7514 r7792  
    2121
    2222using System;
     23using System.Linq;
    2324using HeuristicLab.Common;
    2425using HeuristicLab.Core;
     26using HeuristicLab.Data;
    2527using HeuristicLab.Parameters;
    2628using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    … …  
    3941    private const string GlobalTraceMapParameterName = "GlobalTraceMap";
    4042    private const string GlobalCloneMapParameterName = "GlobalCloneMap";
     43    private const string GlobalFragmentMapParameterName = "GlobalFragmentMap";
    4144
    4245    #region Parameter Properties
    … …  
    4952    public LookupParameter<TraceMapType> GlobalTraceMapParameter {
    5053      get { return (LookupParameter<TraceMapType>)Parameters[GlobalTraceMapParameterName]; }
     54    }
     55    public LookupParameter<CloneMapType> GlobalFragmentMapParameter {
     56      get { return (LookupParameter<CloneMapType>)Parameters[GlobalFragmentMapParameterName]; }
    5157    }
    5258    #endregion
    … …  
    6268      get { return GlobalTraceMapParameter.ActualValue; }
    6369    }
     70    public CloneMapType GlobalFragmentMap {
     71      get { return GlobalFragmentMapParameter.ActualValue; }
     72    }
    6473    #endregion
    6574
    … …  
    7281      Parameters.Add(new LookupParameter<CloneMapType>(GlobalCloneMapParameterName, "A global map keeping track of trees and their clones (made during selection)."));
    7382      Parameters.Add(new LookupParameter<TraceMapType>(GlobalTraceMapParameterName, "A global cache containing tracing info."));
     83      Parameters.Add(new LookupParameter<CloneMapType>(GlobalFragmentMapParameterName, "A global map keeping track of tree fragments received via crossover."));
    7484    }
    7585
    … …  
    7787      ISymbolicExpressionTree tree = SymbolicExpressionTreeParameter.ActualValue;
    7888
    79       if (GlobalTraceMap == null) {
    80         var gScope = ExecutionContext.Scope;
    81         while (gScope.Parent != null) gScope = gScope.Parent;
     89      var gScope = ExecutionContext.Scope;
     90      while (gScope.Parent != null)
     91        gScope = gScope.Parent;
     92
     93      if (GlobalTraceMap == null)
    8294        gScope.Variables.Add(new Variable(GlobalTraceMapParameterName, new TraceMapType()));
    83       }
     95      if (GlobalFragmentMap == null)
     96        gScope.Variables.Add(new Variable(GlobalFragmentMapParameterName, new CloneMapType()));
     97
    8498      if (GlobalTraceMap.ContainsKey(tree)) {
    8599        // tree was affected by crossover before mutation
    86         // if the tree to be manipulated is already a product of crossover (in the current reproduction phase), then there exists no relationship with the original "parent".
     100        // if the tree to be manipulated is already a product of crossover (in the current reproduction phase),
     101        // then there exists no relationship with the original "parent".
    87102        // In order to preserve information, a tree clone is created before mutation and added to the trace map.
    88103        var clone = (IItem)tree.Clone();
    89104        GlobalTraceMap[clone] = GlobalTraceMap[tree];
    90105        GlobalTraceMap[tree] = new ItemList<IItem> { clone };
     106        GlobalFragmentMap[clone] = GlobalFragmentMap[tree];
    91107      } else {
    92108        var original = GlobalCloneMap[tree];
    93109        GlobalTraceMap[tree] = new ItemList<IItem> { original };
    94110      }
     111      var nodes0 = tree.IterateNodesBreadth().ToList();
    95112      Manipulate(RandomParameter.ActualValue, tree);
     113      var nodes1 = tree.IterateNodesBreadth().ToList();
     114      int i, min = Math.Max(nodes0.Count, nodes1.Count);
     115      for (i = 0; i != min; ++i)
     116        if (nodes0[i] != nodes1[i]) break;
     117      if (i == min) i = 0;
     118      GlobalFragmentMap[tree] = new IntValue(i);
    96119
    97120      return base.Apply();

  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Plugin.cs

    r7788 r7792  
    2626
    2727namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
    28   [Plugin("HeuristicLab.Encodings.SymbolicExpressionTreeEncoding","Provides operators and related classes for the symbolic expression tree encoding.", "3.4.2.7785")]
     28  [Plugin("HeuristicLab.Encodings.SymbolicExpressionTreeEncoding","Provides operators and related classes for the symbolic expression tree encoding.", "3.4.2.7788")]
    2929  [PluginFile("HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.dll", PluginFileType.Assembly)]
    3030  [PluginDependency("HeuristicLab.Analysis", "3.3")]

  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/SymbolicExpressionTree.cs

    r7439 r7792  
    8585      return root.IterateNodesPostfix();
    8686    }
     87    public IEnumerable<ISymbolicExpressionTreeNode> IterateNodesBreadth() {
     88      if (root == null)
     89        return new SymbolicExpressionTreeNode[0];
     90      return root.IterateNodesBreadth();
     91    }
    8792
    8893    public override IDeepCloneable Clone(Cloner cloner) {

  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/SymbolicExpressionTreeMatching.cs

    r7788 r7792  
    7070
    7171    public static bool ContainsFragment(this ISymbolicExpressionTree tree, ISymbolicExpressionTreeNode fragment, int mode) {
    72       var nodes = tree.IterateNodesPostfix().ToArray();
    73       var fragments = fragment.IterateNodesPostfix().ToArray();
     72      var nodes = tree.IterateNodesBreadth() as List<ISymbolicExpressionTreeNode>;
     73      var fragments = fragment.IterateNodesBreadth() as List<ISymbolicExpressionTreeNode>;
    7474      return FindMatch(nodes, fragments, mode) != -1;
    7575    }
    7676
    77     #region FindMatch signatures
    78     public static int FindMatch(ISymbolicExpressionTree t0, ISymbolicExpressionTree t1, int mode) {
    79       return FindMatch(t0.IterateNodesPostfix().ToArray(), t1.IterateNodesPostfix().ToArray(), mode);
    80     }
    81     private static int FindMatch(ISymbolicExpressionTreeNode t0, ISymbolicExpressionTreeNode t1, int mode) {
    82       return FindMatch(t0.IterateNodesPostfix().ToArray(), t1.IterateNodesPostfix().ToArray(), mode);
    83     }
    84     private static int FindMatch(ISymbolicExpressionTree t0, ISymbolicExpressionTreeNode t1, int mode) {
    85       return FindMatch(t0.IterateNodesPostfix().ToArray(), t1.IterateNodesPostfix().ToArray(), mode);
    86     }
    87     private static int FindMatch(ISymbolicExpressionTreeNode t0, ISymbolicExpressionTree t1, int mode) {
    88       return FindMatch(t0.IterateNodesPostfix().ToArray(), t1.IterateNodesPostfix().ToArray(), mode);
    89     }
    90     #endregion
    91 
    9277    // convenience methods for less typing :)
    9378    private static IEnumerator<ISymbolicExpressionTreeNode> Enumerator(this ISymbolicExpressionTree tree) {
    94       return tree.IterateNodes().GetEnumerator();
     79      return tree.IterateNodesBreadth().GetEnumerator();
    9580    }
    9681    private static IEnumerator<ISymbolicExpressionTreeNode> Enumerator(this ISymbolicExpressionTreeNode tree) {
    97       return tree.IterateNodes().GetEnumerator();
     82      return tree.IterateNodesBreadth().GetEnumerator();
    9883    }
    99     // method for breath-width iteration of nodes
    100     public static IEnumerable<ISymbolicExpressionTreeNode> IterateNodes(this ISymbolicExpressionTree tree) {
    101       return IterateNodes(tree.Root);
     84    public static int FindMatch(ISymbolicExpressionTree a, ISymbolicExpressionTree b, int mode) {
     85      var nodesA = a.IterateNodesBreadth() as List<ISymbolicExpressionTreeNode>;
     86      var nodesB = b.IterateNodesBreadth() as List<ISymbolicExpressionTreeNode>;
     87      return FindMatch(nodesA, nodesB, mode);
    10288    }
    103 
    104     private static IEnumerable<ISymbolicExpressionTreeNode> IterateNodes(this ISymbolicExpressionTreeNode root) {
    105       var list = new List<ISymbolicExpressionTreeNode> { root };
    106       int offset = 0, count = 1;
    107       while (offset != count) {
    108         var c = count;
    109         for (int i = offset; i != count; ++i) {
    110           yield return list[i]; // TODO: look into yield performance (vs returning the whole list at the end)
    111           if (!list[i].Subtrees.Any()) continue;
    112           list.AddRange(list[i].Subtrees);
    113         }
    114         offset = c;
    115         count = list.Count;
    116       }
    117       //return list;
     89    public static int FindMatch(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b, int mode) {
     90      var nodesA = a.IterateNodesBreadth() as List<ISymbolicExpressionTreeNode>;
     91      var nodesB = b.IterateNodesBreadth() as List<ISymbolicExpressionTreeNode>;
     92      return FindMatch(nodesA, nodesB, mode);
    11893    }
    119 
    120     /// <summary>
    121     /// This method finds the point where parent and child differ. For instance in the case of crossover,
    122     /// it will return the node that was swapped into parent0 from parent1
    123     /// Prerequisites: as the naming implies, heredity should exist between parent and child,
    124     /// otherwise this method would not make much sense (it would always return the root of child)
    125     /// </summary>
    126     /// <param name="parent">The individual from the previous generation that was crossed over or mutated to produce child</param>
    127     /// <param name="child">The result of a genetic operation applied on parent</param>
    128     /// <returns>A symbolic expression tree node representing the difference fragment between parent and child</returns>
    129     public static ISymbolicExpressionTreeNode GetFragmentDiff(ISymbolicExpressionTree parent, ISymbolicExpressionTree child) {
    130       var nodes1 = parent.IterateNodes().ToList();
    131       var nodes2 = child.IterateNodes().ToList();
    132       var e1 = nodes1.AsEnumerable().GetEnumerator();
    133       var e2 = nodes2.AsEnumerable().GetEnumerator();
    134       while (e1.MoveNext() && e2.MoveNext()) {
    135         var comparer = new SymbolicExpressionTreeNodeComparer((int)SimilarityLevel.Exact);
    136         if (!comparer.Equals(e1.Current, e2.Current)) {
    137           return e2.Current;
    138         }
    139         //if (!e1.Current.IterateNodes().SequenceEqual(e2.Current.IterateNodes(), comparer)) {
    140         //  return e2.Current;
    141         //} // return the fragment by which child differs from parent
    142       }
    143       return null;
    144     }
    145 
    14694    // returns the index in the sequence 'seq', where pattern 'pat' is matched, or -1 for no match
    14795    // -1 means no match, 0 means perfect match (the sequences overlap, hence the match index is 0)
    148     public static int FindMatch(ISymbolicExpressionTreeNode[] seq, ISymbolicExpressionTreeNode[] pat, int mode) {
    149       int patlen = pat.Length;
    150       int seqlen = seq.Length;
     96    public static int FindMatch(List<ISymbolicExpressionTreeNode> seq, List<ISymbolicExpressionTreeNode> pat, int mode) {
     97      int patlen = pat.Count;
     98      int seqlen = seq.Count;
    15199      if (patlen == 0 || seqlen == 0) return -1;
    152100      var comparer = new SymbolicExpressionTreeNodeComparer(mode);

  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/SymbolicExpressionTreeNode.cs

    r7522 r7792  
    172172    }
    173173
     174    public IEnumerable<ISymbolicExpressionTreeNode> IterateNodesBreadth() {
     175      var list = new List<ISymbolicExpressionTreeNode>(GetLength()) { this };
     176      int offset = 0, count = 1;
     177      while (offset != count) {
     178        var c = count;
     179        for (int i = offset; i != count; ++i)
     180          if (list[i].SubtreeCount > 0)
     181            list.AddRange(list[i].Subtrees);
     182        offset = c;
     183        count = list.Count;
     184      }
     185      return list;
     186    }
     187
    174188    public IEnumerable<ISymbolicExpressionTreeNode> IterateNodesPrefix() {
    175       List<ISymbolicExpressionTreeNode> list = new List<ISymbolicExpressionTreeNode>();
     189      List<ISymbolicExpressionTreeNode> list = new List<ISymbolicExpressionTreeNode>(GetLength());
    176190      ForEachNodePrefix((n) => list.Add(n));
    177191      return list;
    … …  
    188202
    189203    public IEnumerable<ISymbolicExpressionTreeNode> IterateNodesPostfix() {
    190       List<ISymbolicExpressionTreeNode> list = new List<ISymbolicExpressionTreeNode>();
     204      List<ISymbolicExpressionTreeNode> list = new List<ISymbolicExpressionTreeNode>(GetLength());
    191205      ForEachNodePostfix((n) => list.Add(n));
    192206      return list;

  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking.Views/3.4/GenealogyGraphChart.cs

    r7785 r7792  
    114114              style = DashStyle.Dash;
    115115            } else {
    116               style = arc.OperatorType == 0 ? DashStyle.Solid : DashStyle.Dash;
     116              style = node.InEdges.Count == 2 ? DashStyle.Solid : DashStyle.Dash;
    117117            }
    118118            var arcPen = new Pen(Color.Transparent) { DashStyle = style };
    … …  
    183183                var end = new Point((int)arc.End.X, (int)arc.End.Y);
    184184                arc.Pen.Brush = new LinearGradientBrush(start, end, arc.Source.ToColor(), arc.Target.ToColor());
    185                 if (node.Data.CutpointIndex == -1) {
    186                   // if the cut index wasn't computed yet
    187                   var parent = arc.Source.Data.Data as ISymbolicExpressionTree;
    188                   var child = node.Data.Data as ISymbolicExpressionTree;
    189                   node.Data.CutpointIndex = GetCutIndex(parent, child);
    190                 }
    191185              }
    192186            }
    … …  
    236230      Chart.EnforceUpdate();
    237231    }
    238 
    239     // maybe this method does't belong here
    240     // TODO: find a good location for this kind of functionality
    241     private static int GetCutIndex(ISymbolicExpressionTree parent, ISymbolicExpressionTree child) {
    242       var e1 = parent.IterateNodesPostfix().GetEnumerator();
    243       var e2 = child.IterateNodesPostfix().GetEnumerator();
    244       int pos = 0;
    245       var comparer = new SymbolicExpressionTreeNodeComparer((int)SymbolicExpressionTreeMatching.SimilarityLevel.Exact);
    246       while (e1.MoveNext() && e2.MoveNext() && comparer.Equals(e1.Current, e2.Current)) ++pos;
    247       if (pos == 0) return -1;
    248       if (pos == child.Length) return 0;
    249       return pos;
    250       //return pos == 0 ? -1 : pos;
    251     }
    252232  }
    253233}

  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking.Views/3.4/GenealogyGraphView.cs

    r7785 r7792  
    2121
    2222using System;
     23using System.Collections.Generic;
    2324using System.Drawing;
    2425using System.Linq;
    … …  
    9293      symbolicExpressionTreeChart.Tree = (ISymbolicExpressionTree)genealogyGraphNode.Data;
    9394      if (_selectedVisualSymbolicExpressionTreeNode != null) {
    94         var nodes = symbolicExpressionTreeChart.Tree.IterateNodesPostfix().ToArray();
    95         var fragments = _selectedVisualSymbolicExpressionTreeNode.SymbolicExpressionTreeNode.IterateNodesPostfix().ToArray();
     95        var nodes = symbolicExpressionTreeChart.Tree.IterateNodesBreadth() as List<ISymbolicExpressionTreeNode>;
     96        var fragments = _selectedVisualSymbolicExpressionTreeNode.SymbolicExpressionTreeNode.IterateNodesBreadth() as List<ISymbolicExpressionTreeNode>;
    9697        int index = SymbolicExpressionTreeMatching.FindMatch(nodes, fragments, similarityModeSelector.SelectedIndex);
    9798        if (index != -1) {
    98           _selectedVisualSymbolicExpressionTreeNode = symbolicExpressionTreeChart.GetVisualSymbolicExpressionTreeNode(nodes[index + fragments.Count() - 1]);
     99          _selectedVisualSymbolicExpressionTreeNode = symbolicExpressionTreeChart.GetVisualSymbolicExpressionTreeNode(nodes[index + fragments.Count - 1]);
    99100          var subtree = _selectedVisualSymbolicExpressionTreeNode.SymbolicExpressionTreeNode;
    100101          foreach (var visualNode in subtree.IterateNodesPostfix().Select(node => symbolicExpressionTreeChart.GetVisualSymbolicExpressionTreeNode(node))) {
    … …  
    104105        }
    105106      }
    106       // the cutpoint index represents the index of the node/subtree (when the tree is enumerated in postfix order)
    107       // that was changed (by mutation) or received from a parent (by crossover)
    108       if (visualGenealogyGraphNode.Data.CutpointIndex != -1) {
    109         var gNode = visualGenealogyGraphNode.Data;
    110         var symbExprTree = gNode.Data as ISymbolicExpressionTree;
    111         if (symbExprTree == null) return;
    112         var nodes = symbExprTree.IterateNodesPostfix();
    113         var fragment = nodes.ElementAt(gNode.CutpointIndex);
    114         if (fragment != null) foreach (var node in fragment.IterateNodesPostfix()) {
    115             var visualNode = symbolicExpressionTreeChart.GetVisualSymbolicExpressionTreeNode(node);
    116             visualNode.FillColor = Color.LightPink;
    117           }
    118         symbolicExpressionTreeChart.Repaint();
    119       }
     107      // what's left to be done here is to:
     108      // - get the symbolic expression tree
     109      // - get the corresponding fragment
     110      // - for all symbolic expression tree nodes in the fragment, colorize the corresponding visual nodes
     111      // - repaint the tree
    120112    }
    121113

  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/Analyzers/SymbolicExpressionTreeFragmentsAnalyzer.cs

    r7788 r7792  
    2020#endregion
    2121
     22using System;
    2223using System.Collections.Generic;
    2324using System.Linq;
    … …  
    162163        ResultCollection results = ResultsParameter.ActualValue;
    163164        if (FragmentStatistics == null) {
    164           FragmentStatisticsParameter.ActualValue = new DataTable("Fragment Statistics",
    165                                                                   "Statistical measurements of fragments aggregated over the whole population");
     165          FragmentStatisticsParameter.ActualValue = new DataTable("Fragment Statistics", "Statistical measurements of fragments aggregated over the whole population");
    166166          FragmentStatistics.VisualProperties.YAxisTitle = "Fragment length/Similarities";
    167167          results.Add(new Result("Fragment Statistics", FragmentStatistics));
    … …  
    177177        var trees = (from s in gScope.SubScopes select s.Variables.First().Value as ISymbolicExpressionTree).ToList();
    178178        foreach (var tree in trees.Where(x => GlobalTraceMap.ContainsKey(x))) {
    179           if (GlobalTraceMap[tree].Count == 2) {
    180             var fragment = tree.IterateNodes().ElementAt(((IntValue)GlobalFragmentMap[tree]).Value);
    181             if (fragment != null) {
    182               parents.AddRange(GlobalTraceMap[tree].Cast<ISymbolicExpressionTree>());
    183               fragments.Add(fragment);
    184             } else { // "intermediate crossovers" (immediately followed by mutation)
    185               var parent0 = (ISymbolicExpressionTree)GlobalTraceMap[tree][0];
    186               if (GlobalTraceMap.ContainsKey(parent0)) {
    187                 var p = (ISymbolicExpressionTree)GlobalTraceMap[parent0][0];
    188                 fragment = parent0.IterateNodes().ElementAt(((IntValue)GlobalFragmentMap[parent0]).Value);
    189                 if (fragment != null) {
    190                   parents.AddRange(GlobalTraceMap[parent0].Cast<ISymbolicExpressionTree>());
    191                   fragments.Add(fragment);
    192                 }
    193               }
    194             }
     179          if (GlobalTraceMap[tree].Count == 2) { // crossover
     180            var nodes = tree.IterateNodesBreadth() as List<ISymbolicExpressionTreeNode>;
     181            var index = ((IntValue)GlobalFragmentMap[tree]).Value;
     182            var fragment = nodes[index];
     183            if (fragment == null) throw new ArgumentException("Fragment not found");
     184            parents.AddRange(GlobalTraceMap[tree].Cast<ISymbolicExpressionTree>());
     185            fragments.Add(fragment);
     186          } else { // crossover followed by mutation
     187            // maybe mutation fragments should be also taken into account?
     188            var parent0 = (ISymbolicExpressionTree)GlobalTraceMap[tree][0];
     189            if (!GlobalFragmentMap.ContainsKey(parent0)) throw new ArgumentException("Fragment not found");
     190            var nodes = parent0.IterateNodesBreadth() as List<ISymbolicExpressionTreeNode>;
     191            var index = ((IntValue)GlobalFragmentMap[parent0]).Value;
     192            var fragment = nodes[index];
     193            fragments.Add(fragment);
     194            if (!GlobalTraceMap.ContainsKey(parent0)) throw new ArgumentException("Parent information not found");
     195            parents.AddRange(GlobalTraceMap[parent0].Cast<ISymbolicExpressionTree>());
    195196          }
    196197        }
    … …  
    201202        double a3 = parents.Average(x => x.Length);
    202203        double s1 = CalculateSimilarity(fragments, (int)SymbolicExpressionTreeMatching.SimilarityLevel.Exact);
    203         //double s2 = CalculateSimilarity(fragments, (int)SymbolicExpressionTreeMatching.SimilarityLevel.High);
    204         //double s3 = CalculateSimilarity(fragments, (int)SymbolicExpressionTreeMatching.SimilarityLevel.Relaxed);
    205204
    206205        #region Table data
    207206        // fragments
    208207        if (!FragmentStatistics.Rows.ContainsKey("Average fragment length")) {
    209           DataRow row = new DataRow("Average fragment length", "");
    210           row.VisualProperties.StartIndexZero = true;
     208          var row = new DataRow("Average fragment length", "") { VisualProperties = { StartIndexZero = true } };
    211209          FragmentStatistics.Rows.Add(row);
    212210        }
    … …  
    214212        // child trees
    215213        if (!FragmentStatistics.Rows.ContainsKey("Average child length")) {
    216           DataRow row = new DataRow("Average child length", "");
    217           row.VisualProperties.StartIndexZero = true;
     214          var row = new DataRow("Average child length", "") { VisualProperties = { StartIndexZero = true } };
    218215          FragmentStatistics.Rows.Add(row);
    219216        }
    … …  
    221218        // parents
    222219        if (!FragmentStatistics.Rows.ContainsKey("Average parent length")) {
    223           DataRow row = new DataRow("Average parent length", "");
    224           row.VisualProperties.StartIndexZero = true;
     220          var row = new DataRow("Average parent length", "") { VisualProperties = { StartIndexZero = true } };
    225221          FragmentStatistics.Rows.Add(row);
    226222        }
    … …  
    228224        // exact similarity
    229225        if (!FragmentStatistics.Rows.ContainsKey("Similarity (exact)")) {
    230           DataRow row = new DataRow("Similarity (exact)", "");
    231           row.VisualProperties.StartIndexZero = true;
     226          var row = new DataRow("Similarity (exact)", "") { VisualProperties = { StartIndexZero = true } };
    232227          FragmentStatistics.Rows.Add(row);
    233228        }
    234229        FragmentStatistics.Rows["Similarity (exact)"].Values.Add(s1);
    235         // high similarity
    236         //if (!FragmentStatistics.Rows.ContainsKey("Similarity (high)")) {
    237         //  DataRow row = new DataRow("Similarity (high)", "");
    238         //  row.VisualProperties.StartIndexZero = true;
    239         //  FragmentStatistics.Rows.Add(row);
    240         //}
    241         //FragmentStatistics.Rows["Similarity (high)"].Values.Add(s2);
    242         //// relaxed similarity
    243         //if (!FragmentStatistics.Rows.ContainsKey("Similarity (relaxed)")) {
    244         //  DataRow row = new DataRow("Similarity (relaxed)", "");
    245         //  row.VisualProperties.StartIndexZero = true;
    246         //  FragmentStatistics.Rows.Add(row);
    247         //}
    248         //FragmentStatistics.Rows["Similarity (relaxed)"].Values.Add(s3);
    249230        #endregion
    250231
    … …  
    252233
    253234        // clear the global maps to save memory
    254         GlobalCloneMap.Clear();
    255         GlobalTraceMap.Clear();
     235        if (this.Successor == null || !(this.Successor is SymbolicExpressionTreeGenealogyAnalyzer)) {
     236          GlobalCloneMap.Clear();
     237          GlobalTraceMap.Clear();
     238        }
    256239        GlobalFragmentMap.Clear();
    257240      }
    … …  
    315298    #endregion
    316299
     300    /// <summary>
     301    /// Provide a measure of how similar the fragments that get passed by crossover from one generation to the next are.
     302    /// </summary>
     303    /// <param name="fragments">The symbolic expression tree fragments</param>
     304    /// <param name="mode">The similarity mode (0 - exact, 1 - high, 2 - relaxed)</param>
     305    /// <returns>The average number of similar fragments</returns>
    317306    private double CalculateSimilarity(List<ISymbolicExpressionTreeNode> fragments, int mode) {
    318       bool[] visited = new bool[fragments.Count];
    319       int count = 0;
     307      var visited = new bool[fragments.Count];
     308      int groups = 0;
    320309      for (int i = 0; i != fragments.Count - 1; ++i) {
    321310        if (visited[i]) continue;
    … …  
    324313          if (fragments[i].IsSimilarTo(fragments[j], mode)) visited[j] = true;
    325314        }
    326         ++count;
    327       }
    328       return (double)fragments.Count / count;
     315        ++groups;
     316      }
     317      return (double)fragments.Count / groups;
    329318    }
    330319    #endregion

  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/Analyzers/SymbolicExpressionTreeGenealogyAnalyzer.cs

    r7785 r7792  
    2121
    2222using System;
    23 using System.Collections.Generic;
    2423using System.Drawing;
    2524using System.Globalization;
    … …  
    219218          Results.Add(new Result(PopulationGraphResultParameterName, PopulationGraphResultParameterDescription, graph));
    220219        } else {
    221           //graph = (SymbolicExpressionTreeGenealogyGraph)Results[PopulationGraphResultParameterName].Value;
    222220          graph = (SymbolicExpressionTreeGenealogyGraph)(Results[PopulationGraphResultParameterName].Value);
    223221        }
    … …  
    233231        string label;
    234232        if (generation == 0) {
    235           // at generation 0 no trace map is present (since no reproduction has taken place yet), so we only add the initial trees as nodes in the genealogy graph
     233          // at generation 0 no trace map is present (since no reproduction has taken place yet),
     234          // so we only add the initial individuals as nodes in the genealogy graph
    236235          for (int i = 0; i != qualities.Count; ++i) {
    237236            var tree = qualities.ElementAt(i).Key;
    … …  
    246245          var child = qualities.ElementAt(i).Key;
    247246          label = (generation * qualities.Count + i + 1).ToString(CultureInfo.InvariantCulture);
    248           if (!graph.HasNode(child)) graph.AddNode(child, qualities[child], label, generation, i < Elites.Value);
     247          if (!graph.HasNode(child))
     248            graph.AddNode(child, qualities[child], label, generation, i < Elites.Value);
    249249          if (!GlobalTraceMap.ContainsKey(child)) continue;
    250250          var parents = GlobalTraceMap[child];
    … …  
    264264
    265265        // clear trace and clone maps in preparation for the next generation
    266         GlobalTraceMap.Clear();
    267         GlobalCloneMap.Clear();
     266        if (this.Successor == null || !(this.Successor is SymbolicExpressionTreeFragmentsAnalyzer)) {
     267          GlobalTraceMap.Clear();
     268          GlobalCloneMap.Clear();
     269        }
    268270
    269271        #region end of the run (code for writing results to dot files)
    … …  
    315317    }
    316318
    317  
     319
    318320
    319321    private double Evaluate(ISymbolicExpressionTree tree) {

  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/GenealogyGraph.cs

    r7785 r7792  
    9595    /// <param name="rank">The node rank</param>
    9696    /// <param name="elite">Specifies if this node is an elite</param>
    97     public void AddNode(T t, double quality = 0.0, string label = "", double rank = 0, bool elite = false, int cutIndex = -1) {
     97    public void AddNode(T t, double quality = 0.0, string label = "", double rank = 0, bool elite = false) {
    9898      if (HasNode(t)) return;
    99       _dictionary[t] = new GenealogyGraphNode { Data = t, Quality = quality, Label = label, IsElite = elite, Rank = rank, CutpointIndex = cutIndex };
     99      _dictionary[t] = new GenealogyGraphNode { Data = t, Quality = quality, Label = label, IsElite = elite, Rank = rank };
    100100    }
    101101
    … …  
    103103    ///  more of a low level method to minimize memory usage when creating and returning subgraphs
    104104    /// </summary>
    105     /// <param name="n">The node to be added</param>
    106     public void AddNode(GenealogyGraphNode n) {
    107       var t = (T)n.Data;
     105    /// <param name="node">The node to be added</param>
     106    public void AddNode(GenealogyGraphNode node) {
     107      var t = (T)node.Data;
    108108      if (HasNode(t)) return;
    109       _dictionary[t] = n;
     109      _dictionary[t] = node;
    110110    }
    111111
    … …  
    116116    public void RemoveNode(T t) {
    117117      if (!_dictionary.ContainsKey(t)) return;
    118       GenealogyGraphNode n = _dictionary[t];
    119       if (n.InEdges != null) {
    120         foreach (var e in n.InEdges.Where(e => e.Target.OutEdges != null)) {
    121           e.Target.OutEdges.RemoveAll(arc => arc.Target == n);
     118      var node = _dictionary[t];
     119      if (node.InEdges != null) {
     120        foreach (var e in node.InEdges.Where(e => e.Target.OutEdges != null)) {
     121          e.Target.OutEdges.RemoveAll(arc => arc.Target == node);
    122122          if (!e.Target.OutEdges.Any())
    123123            e.Target.OutEdges = null; // set to null to be a little more memory efficient
    124124        }
    125         n.InEdges = null;
    126       }
    127       if (n.OutEdges != null) {
    128         foreach (var e in n.OutEdges.Where(e => e.Target.InEdges != null)) {
    129           e.Target.InEdges.RemoveAll(arc => arc.Target == n);
     125        node.InEdges = null;
     126      }
     127      if (node.OutEdges != null) {
     128        foreach (var e in node.OutEdges.Where(e => e.Target.InEdges != null)) {
     129          e.Target.InEdges.RemoveAll(arc => arc.Target == node);
    130130          if (!e.Target.InEdges.Any())
    131131            e.Target.InEdges = null; // set to null to be a little more memory efficient
    132132        }
    133         n.OutEdges = null;
     133        node.OutEdges = null;
    134134      }
    135135      _dictionary.Remove(t);
    … …  
    145145    /// <param name="a"></param>
    146146    /// <param name="b"></param>
    147     /// <param name="label"></param>
    148     public void AddArc(T a, T b, int opType = 0) {
     147    public void AddArc(T a, T b) {
    149148      GenealogyGraphNode src, dest;
    150149      if (!HasNode(a)) {
    … …  
    161160      }
    162161      // add forward and reverse arcs
    163       src.AddForwardArc(dest, opType);
    164       dest.AddReverseArc(src, opType);
    165     }
    166 
    167     public void AddArcs(T[] a, T b, int opType = 0) {
     162      src.AddForwardArc(dest);
     163      dest.AddReverseArc(src);
     164    }
     165
     166    public void AddArcs(T[] a, T b) {
    168167      GenealogyGraphNode src, dest;
    169168      if (!HasNode(b)) {
    … …  
    180179          src = _dictionary[o];
    181180        }
    182         src.AddForwardArc(dest, opType);
    183         dest.AddReverseArc(src, opType);
     181        src.AddForwardArc(dest);
     182        dest.AddReverseArc(src);
    184183      }
    185184    }
    … …  
    193192    public double Quality { get; set; }
    194193    public double Rank { get; set; }
    195     public int CutpointIndex { get; set; }
    196194    public List<GenealogyGraphArc> InEdges { get; set; }
    197195    public List<GenealogyGraphArc> OutEdges { get; set; }
    … …  
    210208      InEdges = node.InEdges;
    211209      OutEdges = node.OutEdges;
    212       CutpointIndex = node.CutpointIndex;
    213     }
    214 
    215     /// <summary>
    216     /// Returns all the ancestors of the current node
    217     /// </summary>
    218     /// <returns></returns>
     210    }
     211
     212    /// <summary>
     213    /// Performs an upward-breath-traversal of the genealogy graph using the nodes InEdges
     214    /// </summary>
     215    /// <returns>All the ancestors of the current node</returns>
    219216    public IEnumerable<GenealogyGraphNode> Ancestors() {
    220217      var nodes = new HashSet<GenealogyGraphNode> { this };
    … …  
    236233
    237234    /// <summary>
    238     /// Returns all the descendants of the current node (identical to above method except for using the OutEdges)
    239     /// </summary>
    240     /// <returns></returns>
     235    /// Performs a downward-breath-traversal of the genealogy graph using the nodes OutEdges
     236    /// </summary>
     237    /// <returns>All the descendants of the current node</returns>
    241238    public IEnumerable<GenealogyGraphNode> Descendants() {
    242239      var nodes = new HashSet<GenealogyGraphNode> { this };
    … …  
    257254    }
    258255
    259     public void AddForwardArc(GenealogyGraphNode target, int opType) {
    260       var e = new GenealogyGraphArc { Target = target, OperatorType = opType };
     256    public void AddForwardArc(GenealogyGraphNode target) {
     257      var e = new GenealogyGraphArc { Target = target };
    261258      if (OutEdges == null) OutEdges = new List<GenealogyGraphArc> { e };
    262259      else OutEdges.Add(e);
    263260    }
    264261
    265     public void AddReverseArc(GenealogyGraphNode target, int opType) {
    266       var e = new GenealogyGraphArc { Target = target, OperatorType = opType };
     262    public void AddReverseArc(GenealogyGraphNode target) {
     263      var e = new GenealogyGraphArc { Target = target };
    267264      if (InEdges == null) InEdges = new List<GenealogyGraphArc> { e };
    268265      else InEdges.Add(e);
    … …  
    289286  public class GenealogyGraphArc {
    290287    public GenealogyGraphNode Target { get; set; }
    291     // OperationType is an identifier for the genetic operation (mutation, crossover) that a graph arc will represent
    292     // So basically it describes which operator was applied to an individual/graph node (the one emitting the arc),
    293     // while Target represents the end result of that operator (node ==GeneticOperation==> Target)
    294     public int OperatorType { get; set; }
    295288    // these two fields are not used, but they might be useful later
    296289    public string Label { get; set; } // might be useful later

  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/Interfaces/IGenealogyGraph.cs

    r7779 r7792  
    3030    bool Any(Func<KeyValuePair<T, GenealogyGraphNode>, bool> predicate); // graph contains any nodes matching the given predicate?
    3131    void Clear(); // clear graph
    32     void AddNode(T t, double quality = 0.0, string label = "", double rank = 0, bool elite = false, int cutIndex = -1);
     32    void AddNode(T t, double quality = 0.0, string label = "", double rank = 0, bool elite = false);
    3333    void RemoveNode(T t); // remove node if contained in the graph
    3434    GenealogyGraphNode GetNode(T t); // return node corresponding to object t, or null
    3535    // arc operation
    36     void AddArc(T source, T target, int opType = 0);
    37     void AddArcs(T[] a, T b, int opType = 0);
     36    void AddArc(T source, T target);
     37    void AddArcs(T[] a, T b);
    3838  }
    3939}

  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Selection/3.3/Plugin.cs

    r7788 r7792  
    2626  /// Plugin class for HeuristicLab.Selection plugin.
    2727  /// </summary>
    28   [Plugin("HeuristicLab.Selection", "3.3.6.7785")]
     28  [Plugin("HeuristicLab.Selection", "3.3.6.7788")]
    2929  [PluginFile("HeuristicLab.Selection-3.3.dll", PluginFileType.Assembly)]
    3030  [PluginDependency("HeuristicLab.Collections", "3.3")]
Note: See TracChangeset for help on using the changeset viewer.