Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
05/10/12 17:17:14 (12 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/HeuristicLab.EvolutionaryTracking/3.4
Files:
4 edited

Legend:

Unmodified
Added
Removed

  • 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}
Note: See TracChangeset for help on using the changeset viewer.