Changeset 7515


Ignore:
Timestamp:
02/24/12 10:59:26 (2 years ago)
Author:
bburlacu
Message:

#1772: Added tracking for mutation operators.

Location:
branches/HeuristicLab.EvolutionaryTracking
Files:
2 added
7 edited

Legend:

Unmodified
Added
Removed
  • branches/HeuristicLab.EvolutionaryTracking

    • Property svn:mergeinfo set to (toggle deleted branches)
      /trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTree3219-3222
  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/Analyzers/SymbolicExpressionTreeGenealogyAnalyzer.cs

    r7479 r7515  
    2424using System.Globalization; 
    2525using System.Linq; 
     26using System.Text; 
     27using System.Threading; 
    2628using HeuristicLab.Common; 
    2729using HeuristicLab.Core; 
     
    3234using HeuristicLab.Parameters; 
    3335using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; 
    34  
    35 using TreeCacheType = HeuristicLab.Core.ItemList<HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ISymbolicExpressionTree>; 
    36 using CloneMapType = HeuristicLab.Core.ItemDictionary<HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ISymbolicExpressionTree, 
    37                                                       HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ISymbolicExpressionTree>; 
    38 using TraceMapType = HeuristicLab.Core.ItemDictionary<HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ISymbolicExpressionTree, 
    39                                                       HeuristicLab.Core.IItemArray<HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ISymbolicExpressionTree>>; 
     36using HeuristicLab.Problems.DataAnalysis; 
     37using HeuristicLab.Problems.DataAnalysis.Symbolic; 
     38 
     39using CloneMapType = HeuristicLab.Core.ItemDictionary<HeuristicLab.Core.IItem, HeuristicLab.Core.IItem>; 
     40using TraceMapType = HeuristicLab.Core.ItemDictionary<HeuristicLab.Core.IItem, HeuristicLab.Core.IItemList<HeuristicLab.Core.IItem>>; 
    4041 
    4142namespace HeuristicLab.EvolutionaryTracking { 
     
    4647  [StorableClass] 
    4748  public sealed class SymbolicExpressionTreeGenealogyAnalyzer : SingleSuccessorOperator, IAnalyzer { 
    48     private const string SymbolicExpressionTreeParameterName = "SymbolicExpressionTree"; 
    4949    private const string UpdateIntervalParameterName = "UpdateInterval"; 
    5050    private const string UpdateCounterParameterName = "UpdateCounter"; 
     
    5555    private const string MaximumSelectionPressureParameterName = "MaximumSelectionPressure"; 
    5656    private const string SelectionPressureParameterName = "SelectionPressure"; 
    57     private const string GlobalTreeCacheParameterName = "GlobalTreeCache"; 
    5857    private const string GlobalTraceMapParameterName = "GlobalTraceMap"; 
    5958    private const string GlobalCloneMapParameterName = "GlobalCloneMap"; 
    6059    private const string PopulationGraphResultParameterName = "PopulationGraph"; 
    6160    private const string PopulationGraphResultParameterDescription = "Individual lineages"; 
     61    private const string SymbolicExpressionInterpreterParameterName = "SymbolicExpressionTreeInterpreter"; 
     62    private const string SymbolicRegressionProblemDataParameterName = "ProblemData"; 
     63    private const string SymbolicDataAnalysisProblemEvaluatorParameterName = "Evaluator"; 
    6264 
    6365    #region Parameter properties 
     
    8688      get { return (LookupParameter<DoubleValue>)Parameters[MaximumSelectionPressureParameterName]; } 
    8789    } 
     90    // problem data, interpreter and evaluator 
     91    public LookupParameter<SymbolicDataAnalysisExpressionTreeInterpreter> SymbolicExpressionInterpreterParameter { 
     92      get { return (LookupParameter<SymbolicDataAnalysisExpressionTreeInterpreter>)Parameters[SymbolicExpressionInterpreterParameterName]; } 
     93    } 
     94    public LookupParameter<RegressionProblemData> SymbolicRegressionProblemDataParameter { 
     95      get { return (LookupParameter<RegressionProblemData>)Parameters[SymbolicRegressionProblemDataParameterName]; } 
     96    } 
     97    public LookupParameter<IEvaluator> SymbolicDataAnalysisProblemEvaluatorParameter { 
     98      get { return (LookupParameter<IEvaluator>)Parameters[SymbolicDataAnalysisProblemEvaluatorParameterName]; } 
     99    } 
    88100    // genealogy global parameters 
    89     public LookupParameter<TreeCacheType> GlobalTreeCacheParameter { 
    90       get { return (LookupParameter<TreeCacheType>)Parameters[GlobalTreeCacheParameterName]; } 
    91     } 
    92101    public LookupParameter<TraceMapType> GlobalTraceMapParameter { 
    93102      get { return (LookupParameter<TraceMapType>)Parameters[GlobalTraceMapParameterName]; } 
     
    126135      get { return MaximumSelectionPressureParameter.ActualValue; } 
    127136    } 
    128     public ItemList<ISymbolicExpressionTree> GlobalTreeCache { 
    129       get { return GlobalTreeCacheParameter.ActualValue; } 
    130     } 
    131     public ItemDictionary<ISymbolicExpressionTree, ISymbolicExpressionTree> GlobalCloneMap { 
     137    public CloneMapType GlobalCloneMap { 
    132138      get { return GlobalCloneMapParameter.ActualValue; } 
    133139    } 
    134     public ItemDictionary<ISymbolicExpressionTree, IItemArray<ISymbolicExpressionTree>> GlobalTraceMap { 
     140    public TraceMapType GlobalTraceMap { 
    135141      get { return GlobalTraceMapParameter.ActualValue; } 
     142    } 
     143    public SymbolicDataAnalysisExpressionTreeInterpreter SymbolicExpressionInterpreter { 
     144      get { return SymbolicExpressionInterpreterParameter.ActualValue; } 
     145    } 
     146    public RegressionProblemData SymbolicRegressionProblemData { 
     147      get { return SymbolicRegressionProblemDataParameter.ActualValue; } 
     148    } 
     149    public IEvaluator SymbolicDataAnalysisEvaluator { 
     150      get { return SymbolicDataAnalysisProblemEvaluatorParameter.ActualValue; } 
    136151    } 
    137152    #endregion 
     
    149164    public SymbolicExpressionTreeGenealogyAnalyzer() 
    150165      : base() { 
    151       Parameters.Add(new ScopeTreeLookupParameter<ISymbolicExpressionTree>(SymbolicExpressionTreeParameterName, "The symbolic expression tree whose length should be calculated.")); 
    152166      Parameters.Add(new LookupParameter<IntValue>(ElitesParameterName, "The number of elites.")); 
    153167      Parameters.Add(new LookupParameter<IntValue>(GenerationsParameterName, "The number of generations so far.")); 
     
    157171      Parameters.Add(new ValueParameter<IntValue>(UpdateIntervalParameterName, "The interval in which the tree length analysis should be applied.", new IntValue(1))); 
    158172      Parameters.Add(new ValueParameter<IntValue>(UpdateCounterParameterName, "The value which counts how many times the operator was called since the last update", new IntValue(0))); 
    159       Parameters.Add(new LookupParameter<TreeCacheType>(GlobalTreeCacheParameterName, "A global list holding all trees from all generations.")); 
    160173      Parameters.Add(new LookupParameter<TraceMapType>(GlobalTraceMapParameterName, "A global cache containing the whole genealogy.")); 
    161174      Parameters.Add(new LookupParameter<CloneMapType>(GlobalCloneMapParameterName, "A global map keeping track of trees and their clones (made during selection).")); 
    162175      Parameters.Add(new ValueLookupParameter<ResultCollection>(ResultsParameterName, "The results collection where the analysis values should be stored.")); 
     176      Parameters.Add(new LookupParameter<SymbolicDataAnalysisExpressionTreeInterpreter>(SymbolicExpressionInterpreterParameterName, "Interpreter for symbolic expression trees")); 
     177      Parameters.Add(new LookupParameter<RegressionProblemData>(SymbolicRegressionProblemDataParameterName, "The symbolic data analysis problem.")); 
     178      Parameters.Add(new LookupParameter<IEvaluator>(SymbolicDataAnalysisProblemEvaluatorParameterName, "The fitness evaluator")); 
    163179 
    164180      UpdateCounterParameter.Hidden = true; 
     
    170186      // check if all the parameters are present and accounted for  
    171187      if (!Parameters.ContainsKey(UpdateIntervalParameterName)) { 
    172         Parameters.Add(new ValueParameter<IntValue>(UpdateIntervalParameterName, 
    173                                                     "The interval in which the tree length analysis should be applied.", 
    174                                                     new IntValue(1))); 
    175       } 
    176       //necessary code to correct UpdateCounterParameter - type was changed from LookupParameter to ValueParameter 
    177       if (Parameters.ContainsKey(UpdateCounterParameterName) && 
    178           (Parameters[UpdateCounterParameterName] is LookupParameter<IntValue>)) 
    179         Parameters.Remove(UpdateCounterParameterName); 
    180       if (!Parameters.ContainsKey(UpdateCounterParameterName)) { 
    181         Parameters.Add(new ValueParameter<IntValue>(UpdateCounterParameterName, 
    182                                                     "The value which counts how many times the operator was called since the last update", 
    183                                                     new IntValue(0))); 
    184         UpdateCounterParameter.Hidden = true; 
    185       } 
     188        Parameters.Add(new ValueParameter<IntValue>(UpdateIntervalParameterName, "The interval in which the tree length analysis should be applied.", new IntValue(1))); 
     189      } 
     190      if (Parameters.ContainsKey(UpdateCounterParameterName)) return; 
     191      Parameters.Add(new ValueParameter<IntValue>(UpdateCounterParameterName, "The value which counts how many times the operator was called since the last update", new IntValue(0))); 
     192      UpdateCounterParameter.Hidden = true; 
    186193    } 
    187194 
     
    206213        var gScope = ExecutionContext.Scope; 
    207214        while (gScope.Parent != null) gScope = gScope.Parent; 
    208  
    209         GenealogyGraph _graph; 
     215        GenealogyGraph graph; 
    210216        if (!Results.ContainsKey(PopulationGraphResultParameterName)) { 
    211           _graph = new GenealogyGraph(); 
    212           Results.Add(new Result(PopulationGraphResultParameterName, PopulationGraphResultParameterDescription, _graph)); 
     217          graph = new GenealogyGraph(); 
     218          Results.Add(new Result(PopulationGraphResultParameterName, PopulationGraphResultParameterDescription, graph)); 
    213219        } else { 
    214           _graph = (GenealogyGraph)Results[PopulationGraphResultParameterName].Value; 
    215         } 
    216  
    217         var treeQualities = (from s in gScope.SubScopes 
    218                              let tree = (SymbolicExpressionTree)s.Variables["SymbolicExpressionTree"].Value 
    219                              let quality = (DoubleValue)s.Variables["Quality"].Value 
    220                              orderby quality.Value descending 
    221                              select new Tuple<ISymbolicExpressionTree, DoubleValue>(tree, quality)).ToList(); 
     220          graph = (GenealogyGraph)Results[PopulationGraphResultParameterName].Value; 
     221        } 
     222        // get tree quality values 
     223        var qualities = (from s in gScope.SubScopes 
     224                         let individual = s.Variables.First().Value 
     225                         let quality = (DoubleValue)s.Variables["Quality"].Value 
     226                         orderby quality.Value descending 
     227                         select new Tuple<IItem, double>(individual, quality.Value)).ToDictionary(t => t.Item1, t => t.Item2); 
     228 
    222229        // add all individuals to the evolutionary graph 
    223         for (int i = 0; i != treeQualities.Count; ++i) { 
    224           var tree = treeQualities[i].Item1; 
    225           var quality = treeQualities[i].Item2; 
    226           if (!_graph.HasNode(tree)) { 
    227             _graph.AddNode(tree, quality.Value, (Generations.Value * treeQualities.Count + i + 1).ToString(CultureInfo.InvariantCulture)); 
    228           } else { 
    229             _graph.GetNode(tree).Label += "\\n" + (Generations.Value * treeQualities.Count + i + 1).ToString(CultureInfo.InvariantCulture); 
     230        int generation = Generations.Value; 
     231        int count = GlobalTraceMap.Count; 
     232        string label; 
     233 
     234        if (generation == 0) { 
     235          // at generation 0 no trace map is present (since no reproduction has taken place yet),  
     236          // so we only add the initial trees as nodes in the genealogy graph 
     237          for (int i = 0; i != qualities.Count; ++i) { 
     238            var tree = qualities.ElementAt(i).Key; 
     239            label = (i + 1).ToString(CultureInfo.InvariantCulture); 
     240            graph.AddNode(tree, qualities[tree], label, generation); 
    230241          } 
    231  
    232           if (GlobalTraceMap == null || !GlobalTraceMap.ContainsKey(tree)) 
    233             continue; 
    234           // get number of parents and adjust label (2 parents => crossover, 1 parent => mutation) 
    235           var parents = GlobalTraceMap[tree]; 
    236           string label = (parents.Count == 2) ? "c" : "m"; 
     242          return base.Apply(); 
     243        } 
     244 
     245        // mark and add elites 
     246        // elites do not appear in the trace map (because they are never the product of a genetic operation) 
     247        var elites = qualities.OrderByDescending(x => x.Value).Take(Elites.Value).Select(x => x.Key).ToList(); 
     248        for (int i = 0; i != Elites.Value; ++i) { 
     249          label = (generation * count + i + 1).ToString(CultureInfo.InvariantCulture); 
     250          var elite = elites[i]; 
     251          if (!graph.HasNode(elite)) 
     252            graph.AddNode(elite, qualities[elite], label, Generations.Value, true); 
     253          else 
     254            graph.GetNode(elite).Label += "\\n" + label; 
     255 
     256          graph.GetNode(elite).Color = new Color { R = 0, G = 100, B = 150 }; 
     257        } 
     258 
     259        for (int i = 0; i != count; ++i) { 
     260          var trace = GlobalTraceMap.ElementAt(i); 
     261          var child = (ISymbolicExpressionTree)trace.Key; 
     262 
     263          if (!graph.HasNode(child)) { 
     264            // due to the structure of the trace map, qualities[child] will never throw an exception, so we use it directly 
     265            label = (generation * count + i + 1 + Elites.Value).ToString(CultureInfo.InvariantCulture); 
     266            graph.AddNode(child, qualities[child], label, generation); 
     267          } 
     268          var parents = trace.Value; 
    237269          foreach (var parent in parents) { 
    238             _graph.AddArc(parent, tree, label); 
     270            if (!graph.HasNode(parent)) { 
     271              // if the node is a clone introduced pre-mutation, then its quality value has to be evaluated 
     272              if (!qualities.ContainsKey(parent)) 
     273                qualities[parent] = Evaluate((ISymbolicExpressionTree)parent); 
     274              label = ((generation - 1) * count + i + 1).ToString(CultureInfo.InvariantCulture); 
     275              graph.AddNode(parent, qualities[parent], label, generation - 1); 
     276            } 
     277            graph.AddArc(parent, child); 
    239278          } 
    240279        } 
    241         if (GlobalTraceMap != null) 
    242           GlobalTraceMap.Clear(); 
    243  
    244         // mark elites 
    245         for (int i = 0; i != Elites.Value; ++i) 
    246           _graph.GetNode(treeQualities[i].Item1).IsElite = true; 
     280        GlobalTraceMap.Clear(); // no need to check for null here (see line 212) 
    247281 
    248282        // if we've reached the end of the run 
    249         if (Generations.Value == MaximumGenerations.Value || 
    250            (SelectionPressureParameter != null && SelectionPressure.Value >= MaximumSelectionPressure.Value)) { 
    251  
     283        bool maxGenerationsReached = (Generations.Value == MaximumGenerations.Value); 
     284        bool isOsga = (SelectionPressure != null && MaximumSelectionPressure != null); 
     285        bool maxSelectionPressureReached = isOsga && (SelectionPressure.Value >= MaximumSelectionPressure.Value); 
     286 
     287        #region end of the run 
     288        if (maxGenerationsReached || maxSelectionPressureReached) { 
    252289          var path = Environment.GetFolderPath(Environment.SpecialFolder.UserProfile); 
    253290 
    254291          // write whole graph to a dot file 
    255           WriteDot(path + @"\lineage.dot", _graph); 
     292          WriteDot(path + @"\lineage.dot", graph); 
    256293 
    257294          // get genealogy of the best solution 
    258           var bestSolution = treeQualities.First().Item1; 
    259           var genealogy = _graph.GetNode(bestSolution).Genealogy(); 
     295          var bestSolution = (ISymbolicExpressionTree)qualities.First().Key; 
     296          var genealogy = graph.GetNode(bestSolution).Genealogy(); 
    260297          WriteDot(path + @"\bestlineage.dot", genealogy); 
     298 
     299          // write the direct root lineage of the best solution (is it useful?) 
     300 
     301          // calculate impact values of nodes in the best solution, attempt to trace those with high impact to their origins 
     302          //var impactValuesCalculator = new RegressionSolutionImpactValuesCalculator(); 
     303          //var impactValues = impactValuesCalculator.CalculateImpactValues(bestSolution, SymbolicExpressionInterpreter, SymbolicRegressionProblemData); 
     304          ////var impactValues = CalculateImpactValues(bestSolution); 
     305          //foreach (var pair in impactValues.Where(pair => !(pair.Key is ConstantTreeNode || pair.Key is VariableTreeNode) && pair.Value > 0.9)) { 
     306          //  var node = pair.Key; 
     307 
     308          //  foreach (var ancestor in genealogy.Keys) { 
     309          //    graph.GetNode(ancestor).Color = ContainsSubtree(ancestor as ISymbolicExpressionTree, node) ? new Color { R = 0, G = 0, B = 150 } : new Color { R = 255, G = 255, B = 255 }; 
     310          //  } 
     311          //} 
     312          //WriteDot(path + @"\impactancestry.dot", genealogy); 
    261313 
    262314          // trim the graph 
    263315          // exclude the individuals of the last generation 
    264           var individuals = _graph.Keys.Except(treeQualities.Select(x => x.Item1)).ToList(); 
     316          var individuals = graph.Keys.Except(qualities.Select(x => x.Key)).ToList(); 
    265317          bool done = false; 
    266318          while (!done) { 
     
    268320            foreach (var ind in individuals) { 
    269321              // if node has no outgoing connections (absence of offspring), remove it from the graph 
    270               var node = _graph.GetNode(ind); 
     322              var node = graph.GetNode(ind); 
    271323              if (node == null) continue; 
    272324              if (node.OutEdges == null) { 
    273325                done = false; // we still have "dead" nodes 
    274                 _graph.RemoveNode(ind); 
     326                graph.RemoveNode(ind); 
    275327              } 
    276328            } 
    277329          } 
    278           WriteDot(path + @"\trimmedlineage.dot", _graph); 
    279         } 
     330          WriteDot(path + @"\trimmedlineage.dot", graph); 
     331        } 
     332        #endregion 
    280333      } 
    281334      return base.Apply(); 
    282335    } 
    283336 
     337    private double Evaluate(ISymbolicExpressionTree tree) { 
     338      // we perform evaluation by adding a temporary subscope with the tree in it, and calling evaluator.Apply() 
     339      var subScope = new Scope(); 
     340      // inject expected variables into the subscope 
     341      subScope.Variables.Add(new Core.Variable("SymbolicExpressionTree", tree)); 
     342      ExecutionContext.Scope.SubScopes.Add(subScope); 
     343      var context = new Core.ExecutionContext(ExecutionContext, SymbolicDataAnalysisEvaluator, subScope); 
     344      SymbolicDataAnalysisEvaluator.Execute(context, new CancellationToken()); 
     345      // get the quality 
     346      double quality = ((DoubleValue)subScope.Variables["Quality"].Value).Value; 
     347      // remove the subscope 
     348      ExecutionContext.Scope.SubScopes.Remove(subScope); 
     349      return quality; 
     350    } 
     351 
     352    #region Export to dot file 
    284353    private static void WriteDot(string path, GenealogyGraph graph) { 
    285354      using (var file = new System.IO.StreamWriter(path)) { 
    286355        string nl = Environment.NewLine; 
    287         file.WriteLine("digraph \"lineage " + graph.AverageDegree.ToString() + "\" {" + nl + 
     356        file.WriteLine("digraph \"lineage " + graph.AverageDegree.ToString(CultureInfo.InvariantCulture) + "\" {" + nl + 
    288357                       "ratio=auto;" + nl + 
    289358                       "mincross=2.0"); 
     
    291360 
    292361        foreach (var node in graph.Values) { 
    293           var quality = node.Quality; 
    294           string fillColor = String.Format("#{0:x2}{1:x2}{2:x2}", (int)(255 - 255 * quality), (int)(255 * quality), (int)(100 * quality)); 
     362          string fillColor = String.Format("#{0:x2}{1:x2}{2:x2}", node.Color.R, node.Color.G, node.Color.B); 
    295363          if (node.IsElite) 
    296             fillColor = String.Format("#{0:x2}{1:x2}{2:x2}", (int)(255 - 255 * quality), (int)(255 * quality), (int)(255 * quality)); 
     364            fillColor = String.Format("#{0:x2}{1:x2}{2:x2}", node.Color.R, node.Color.G, 150); 
    297365          file.WriteLine("\t\"" + node.Id + "\" [fillcolor=\"" + fillColor + "\",label=\"" + node.Label + "\"];"); 
    298366          if (node.InEdges == null) 
    299367            continue; 
    300           foreach (var edge in node.InEdges) 
    301             file.WriteLine("\t\"" + edge.Target.Id + "\" -> \"" + node.Id + "\" [arrowsize=.5, color=\"" + fillColor + "\"];"); 
     368          foreach (var edge in node.InEdges) { 
     369            var edgeStyle = node.InEdges.Count == 1 ? "dashed" : String.Empty; 
     370            file.WriteLine("\t\"" + edge.Target.Id + "\" -> \"" + node.Id + "\" [arrowsize=.5, color=\"" + fillColor + "\", style=\"" + edgeStyle + "\"];"); 
     371          } 
     372        } 
     373        foreach (var g in graph.Values.GroupBy(x => x.Generation)) { 
     374          var sb = new StringBuilder(); 
     375          sb.Append("\t{rank=same;"); 
     376          foreach (var node in g) 
     377            sb.Append("\"" + node.Id + "\" "); 
     378          sb.Append("}\n"); 
     379          file.Write(sb.ToString()); 
    302380        } 
    303381        file.WriteLine("}"); 
    304382      } 
    305383    } 
     384    #endregion 
     385 
     386    #region Impact values (code for calculating to be moved in separate class) 
     387    private Dictionary<ISymbolicExpressionTreeNode, double> CalculateImpactValues(ISymbolicExpressionTree tree) { 
     388      var interpreter = SymbolicExpressionInterpreter; 
     389      var problemData = (IRegressionProblemData)SymbolicDataAnalysisEvaluator.Parameters["ProblemData"].ActualValue; 
     390      var dataset = problemData.Dataset; 
     391      var rows = problemData.TrainingIndizes; 
     392      string targetVariable = problemData.TargetVariable; 
     393      var impactValues = new Dictionary<ISymbolicExpressionTreeNode, double>(); 
     394      var nodes = tree.Root.GetSubtree(0).GetSubtree(0).IterateNodesPostfix().ToList(); 
     395      var originalOutput = interpreter.GetSymbolicExpressionTreeValues(tree, dataset, rows); 
     396      var targetValues = dataset.GetDoubleValues(targetVariable, rows); 
     397      OnlineCalculatorError errorState; 
     398      double originalR2 = OnlinePearsonsRSquaredCalculator.Calculate(targetValues, originalOutput, out errorState); 
     399      if (errorState != OnlineCalculatorError.None) originalR2 = 0.0; 
     400 
     401      var constantNode = ((ConstantTreeNode)new Constant().CreateTreeNode()); 
     402      var root = new ProgramRootSymbol().CreateTreeNode(); // root node 
     403      var start = new StartSymbol().CreateTreeNode(); // start node 
     404      root.AddSubtree(start); 
     405      var tempTree = new SymbolicExpressionTree(root); 
     406 
     407      foreach (ISymbolicExpressionTreeNode node in nodes) { 
     408        var parent = node.Parent; 
     409        constantNode.Value = CalculateReplacementValue(tempTree, node, tree); 
     410        ISymbolicExpressionTreeNode replacementNode = constantNode; 
     411        SwitchNode(parent, node, replacementNode); 
     412        var newOutput = interpreter.GetSymbolicExpressionTreeValues(tree, dataset, rows); 
     413        double newR2 = OnlinePearsonsRSquaredCalculator.Calculate(targetValues, newOutput, out errorState); 
     414        if (errorState != OnlineCalculatorError.None) newR2 = 0.0; 
     415 
     416        // impact = 0 if no change 
     417        // impact < 0 if new solution is better 
     418        // impact > 0 if new solution is worse 
     419        impactValues[node] = originalR2 - newR2; 
     420        SwitchNode(parent, replacementNode, node); 
     421      } 
     422      return impactValues; 
     423    } 
     424 
     425    private double CalculateReplacementValue(ISymbolicExpressionTree tempTree, ISymbolicExpressionTreeNode node, ISymbolicExpressionTree sourceTree) { 
     426      // remove old ADFs 
     427      while (tempTree.Root.SubtreeCount > 1) tempTree.Root.RemoveSubtree(1); 
     428      // clone ADFs of source tree 
     429      for (int i = 1; i < sourceTree.Root.SubtreeCount; i++) { 
     430        tempTree.Root.AddSubtree((ISymbolicExpressionTreeNode)sourceTree.Root.GetSubtree(i).Clone()); 
     431      } 
     432      var start = tempTree.Root.GetSubtree(0); 
     433      while (start.SubtreeCount > 0) start.RemoveSubtree(0); 
     434      start.AddSubtree((ISymbolicExpressionTreeNode)node.Clone()); 
     435      var interpreter = SymbolicExpressionInterpreter; 
     436      var rows = SymbolicRegressionProblemData.TrainingIndizes; 
     437      return interpreter.GetSymbolicExpressionTreeValues(tempTree, SymbolicRegressionProblemData.Dataset, rows).Median(); 
     438    } 
     439 
     440    private static void SwitchNode(ISymbolicExpressionTreeNode root, ISymbolicExpressionTreeNode oldBranch, ISymbolicExpressionTreeNode newBranch) { 
     441      for (int i = 0; i < root.SubtreeCount; i++) { 
     442        if (root.GetSubtree(i) == oldBranch) { 
     443          root.RemoveSubtree(i); 
     444          root.InsertSubtree(i, newBranch); 
     445          return; 
     446        } 
     447      } 
     448    } 
     449    #endregion 
     450 
     451    #region Allele tracking 
     452    private bool ContainsSubtree(ISymbolicExpressionTree tree, ISymbolicExpressionTreeNode node) { 
     453      return tree.IterateNodesPostfix().Where(n => n.Symbol == node.Symbol && n.GetLength() == node.GetLength()) 
     454                                       .Where(n => n.Subtrees.Any() && node.Subtrees.Any()) 
     455                                       .Any(n => n.Subtrees.First().Symbol == node.Subtrees.First().Symbol); 
     456    } 
     457    #endregion 
     458 
     459    #region Extra / not really needed 
     460    private IEnumerable<ISymbolicExpressionTreeNode> IterateNodes(ISymbolicExpressionTree tree) { 
     461      return IterateNodes(tree.Root); 
     462    } 
     463 
     464    private static IEnumerable<ISymbolicExpressionTreeNode> IterateNodes(ISymbolicExpressionTreeNode root) { 
     465      var list = new List<ISymbolicExpressionTreeNode> { root }; 
     466      int offset = 0, count = 1; 
     467      while (offset != count) { 
     468        var c = count; 
     469        for (int i = offset; i != count; ++i) { 
     470          yield return list[i]; 
     471          if (!list[i].Subtrees.Any()) continue; 
     472          list.AddRange(list[i].Subtrees); 
     473        } 
     474        offset = c; 
     475        count = list.Count; 
     476      } 
     477    } 
     478    #endregion 
    306479  } 
    307480} 
  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/GenealogyGraph.cs

    r7479 r7515  
    55using HeuristicLab.Common; 
    66using HeuristicLab.Core; 
    7 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding; 
    87using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; 
    98 
    109namespace HeuristicLab.EvolutionaryTracking { 
    1110  public class GenealogyGraph : NamedItem { 
    12     private readonly Dictionary<ISymbolicExpressionTree, Node> _dictionary; 
     11    private readonly Dictionary<object, Node> _dictionary; 
     12 
    1313    public GenealogyGraph() { 
    14       _dictionary = new Dictionary<ISymbolicExpressionTree, Node>(); 
     14      _dictionary = new Dictionary<object, Node>(); 
    1515    } 
    1616 
    1717    public GenealogyGraph(GenealogyGraph g) { 
    18       _dictionary = new Dictionary<ISymbolicExpressionTree, Node>(g._dictionary); 
     18      _dictionary = new Dictionary<object, Node>(g._dictionary); 
     19    } 
     20 
     21    public override IDeepCloneable Clone(Cloner cloner) { 
     22      return new GenealogyGraph(this, cloner); 
     23    } 
     24 
     25    public override string ItemName { 
     26      get { return "GenealogyGraph"; } 
     27    } 
     28 
     29    public override string ItemDescription { 
     30      get { return "A graph describing the genealogies of all the individuals"; } 
     31    } 
     32 
     33    public new Version ItemVersion { 
     34      get { return new Version(3, 3, 6); } 
     35    } 
     36 
     37    public new Image ItemImage { 
     38      get { return Common.Resources.VSImageLibrary.Graph; } 
    1939    } 
    2040 
    2141    [StorableConstructor] 
    22     private GenealogyGraph(bool serializing) : base(serializing) { } 
     42    private GenealogyGraph(bool serializing) 
     43      : base(serializing) { 
     44    } 
    2345 
    2446    private GenealogyGraph(GenealogyGraph original, Cloner cloner) 
    2547      : base(original, cloner) { 
    26       _dictionary = new Dictionary<ISymbolicExpressionTree, Node>(original._dictionary); 
    27     } 
    28  
    29     public bool HasNode(ISymbolicExpressionTree t) { 
     48      _dictionary = new Dictionary<object, Node>(original._dictionary); 
     49    } 
     50 
     51    public bool HasNode(object t) { 
    3052      return _dictionary.ContainsKey(t); 
    3153    } 
    3254 
    33     public Node GetNode(ISymbolicExpressionTree t) { 
     55    public Node GetNode(object t) { 
    3456      return this.HasNode(t) ? _dictionary[t] : null; 
    3557    } 
    3658 
    37     public IEnumerable<ISymbolicExpressionTree> Keys { 
     59    public IEnumerable<object> Keys { 
    3860      get { return _dictionary.Keys; } 
    3961    } 
     
    4769    } 
    4870 
    49     public bool Any(Func<KeyValuePair<ISymbolicExpressionTree, Node>, bool> predicate) { 
     71    public bool Any(Func<KeyValuePair<object, Node>, bool> predicate) { 
    5072      return _dictionary.Any(predicate); 
    5173    } 
     
    5981    /// </summary> 
    6082    /// <param name="t">The symbolic expression tree</param> 
    61     public void AddNode(ISymbolicExpressionTree t, double q = 0.0, string l = "", bool elite = false) { 
     83    /// <param name="q">The quality value </param> 
     84    /// <param name="l">The node label</param> 
     85    /// <param name="elite">Specifies if this node is an elite</param> 
     86    public void AddNode(object t, double q = 0.0, string l = "", int g = 0, bool elite = false) { 
    6287      if (HasNode(t)) return; 
    63       _dictionary[t] = new Node { Data = t, Quality = q, Label = l, IsElite = elite }; 
     88      var color = new Color { R = (byte)(255 - 255 * q), G = (byte)(255 * q), B = 50 }; 
     89      _dictionary[t] = new Node { Data = t, Quality = q, Label = l, IsElite = elite, Generation = g, Color = color }; 
    6490    } 
    6591 
     
    6995    /// <param name="n"></param> 
    7096    public void AddNode(Node n) { 
    71       var t = (ISymbolicExpressionTree)n.Data; 
     97      var t = n.Data; 
    7298      if (HasNode(t)) 
    7399        return; 
     
    79105    /// </summary> 
    80106    /// <param name="t">The graph node</param> 
    81     public void RemoveNode(ISymbolicExpressionTree t) { 
     107    public void RemoveNode(object t) { 
    82108      if (!_dictionary.ContainsKey(t)) 
    83109        return; 
     
    94120        foreach (var e in n.OutEdges.Where(e => e.Target.InEdges != null)) { 
    95121          e.Target.InEdges.RemoveAll(arc => arc.Target == n); 
    96           if (!e.Target.OutEdges.Any()) 
     122          if (!e.Target.InEdges.Any()) 
    97123            e.Target.InEdges = null; // set to null to be a little more memory efficient 
    98124        } 
     
    112138    /// <param name="b"></param> 
    113139    /// <param name="label"></param> 
    114     public void AddArc(ISymbolicExpressionTree a, ISymbolicExpressionTree b, string label) { 
     140    public void AddArc(object a, object b, string label = "") { 
    115141      Node src, dest; 
    116142      if (!HasNode(a)) { 
     
    131157    } 
    132158 
    133     public override IDeepCloneable Clone(Cloner cloner) { 
    134       return new GenealogyGraph(this, cloner); 
    135     } 
    136  
    137     public override string ItemName { 
    138       get { return "GenealogyGraph"; } 
    139     } 
    140  
    141     public override string ItemDescription { 
    142       get { return "A graph describing the genealogies of all the individuals"; } 
    143     } 
    144  
    145     public new Version ItemVersion { 
    146       get { return new Version(3, 3, 6); } 
    147     } 
    148  
    149     public new Image ItemImage { 
    150       get { return Common.Resources.VSImageLibrary.Graph; } 
     159    public void AddArcs(object[] a, object b, string label) { 
     160      Node src, dest; 
     161      if (!HasNode(b)) { 
     162        dest = new Node { Data = b }; 
     163        _dictionary[b] = dest; 
     164      } else { 
     165        dest = _dictionary[b]; 
     166      } 
     167      foreach (var o in a) { 
     168        if (!HasNode(o)) { 
     169          src = new Node { Data = o }; 
     170          _dictionary[o] = src; 
     171        } else { 
     172          src = _dictionary[o]; 
     173        } 
     174        src.AddForwardArc(dest, label); 
     175        dest.AddReverseArc(src, label); 
     176      } 
    151177    } 
    152178  } 
     
    160186    public object Data { get; set; } 
    161187    public double Quality { get; set; } 
     188    public int Generation { get; set; } 
     189    public Color Color { get; set; } 
    162190 
    163191    public int Degree { 
     
    229257    // other attributes 
    230258  } 
    231  
    232259  // an edge can be represented as a tuple<Node, Node> TODO: figure it out (might be useful for easier querying) 
     260 
     261  public struct Color { 
     262    public byte R { get; set; } 
     263    public byte G { get; set; } 
     264    public byte B { get; set; } 
     265  } 
    233266} 
  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/HeuristicLab.EvolutionaryTracking-3.4.csproj

    r7479 r7515  
    6767    </Reference> 
    6868    <Reference Include="HeuristicLab.PluginInfrastructure-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL" /> 
     69    <Reference Include="HeuristicLab.Problems.DataAnalysis-3.4, Version=3.4.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL" /> 
     70    <Reference Include="HeuristicLab.Problems.DataAnalysis.Symbolic-3.4, Version=3.4.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL" /> 
     71    <Reference Include="HeuristicLab.Problems.DataAnalysis.Symbolic.Regression-3.4, Version=3.4.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL" /> 
     72    <Reference Include="HeuristicLab.Problems.DataAnalysis.Symbolic.Regression.Views-3.4, Version=3.4.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL" /> 
     73    <Reference Include="HeuristicLab.Problems.DataAnalysis.Symbolic.Views-3.4, Version=3.4.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL" /> 
    6974    <Reference Include="Microsoft.GLEE"> 
    7075      <HintPath>..\..\..\..\..\..\..\..\Program Files\Microsoft Research\GLEE\bin\Microsoft.GLEE.dll</HintPath> 
     
    97102    <Compile Include="Plugin.cs" /> 
    98103    <Compile Include="Properties\AssemblyInfo.cs" /> 
     104    <Compile Include="RegressionSolutionImpactValuesCalculator.cs"> 
     105      <SubType>UserControl</SubType> 
     106    </Compile> 
    99107  </ItemGroup> 
    100108  <ItemGroup> 
  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/HeuristicLab.EvolutionaryTracking-3.4.csproj.user

    r7479 r7515  
    22<Project ToolsVersion="4.0" xmlns="http://schemas.microsoft.com/developer/msbuild/2003"> 
    33  <PropertyGroup> 
    4     <ProjectView>ShowAllFiles</ProjectView> 
     4    <ProjectView>ProjectFiles</ProjectView> 
    55  </PropertyGroup> 
    66</Project> 
Note: See TracChangeset for help on using the changeset viewer.