source: branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/SymbolicExpressionTreeGenealogyGraph.cs @ 9419

Last change on this file since 9419 was 9419, checked in by bburlacu, 8 years ago

#1772: Refactoring of directed graph components, added code for correctly serializing vertices and edges. Added specific building blocks analyzers and new population diversity analyzer which correctly integrates with the parallel engine.

File size: 6.8 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2012 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using System;
23using System.Collections.Generic;
24using System.Linq;
25using HeuristicLab.Common;
26using HeuristicLab.Core;
27using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
28using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
29
30namespace HeuristicLab.EvolutionaryTracking {
31  [Item("SymbolicExpressionTreeGenealogyGraph", "A genealogy graph for symbolic expression tree individuals")]
32  [StorableClass]
33  public sealed class SymbolicExpressionTreeGenealogyGraph : GenericGraph<SymbolicExpressionGenealogyGraphNode>,
34                                                             ISymbolicExpressionTreeGenealogyGraph, IDisposable {
35    [Storable]
36    private readonly Dictionary<ISymbolicExpressionTree, List<SymbolicExpressionGenealogyGraphNode>> nodeMap
37      = new Dictionary<ISymbolicExpressionTree, List<SymbolicExpressionGenealogyGraphNode>>();
38
39    public SymbolicExpressionTreeGenealogyGraph() {
40    }
41
42    public void Updated() {
43      var updated = GraphUpdated;
44      if (updated != null) updated(this, null);
45    }
46
47    [StorableConstructor]
48    public SymbolicExpressionTreeGenealogyGraph(bool serializing)
49      : base(serializing) {
50    }
51
52    public override IDeepCloneable Clone(Cloner cloner) {
53      return new SymbolicExpressionTreeGenealogyGraph(this, cloner);
54    }
55
56    private SymbolicExpressionTreeGenealogyGraph(SymbolicExpressionTreeGenealogyGraph original, Cloner cloner)
57      : base(original, cloner) {
58      nodeMap = new Dictionary<ISymbolicExpressionTree, List<SymbolicExpressionGenealogyGraphNode>>(original.nodeMap);
59    }
60
61    public override void AddNode(SymbolicExpressionGenealogyGraphNode node) {
62      var tree = node.SymbolicExpressionTree;
63      if (nodeMap.ContainsKey(tree))
64        nodeMap[tree].Add(node);
65      else
66        nodeMap[tree] = new List<SymbolicExpressionGenealogyGraphNode> { node };
67      base.AddNode(node);
68      // the genealogy graph should have as many nodes as individuals in the population multiplied by the number of generations
69      // plus a number of intermediate individuals ~= mutation probability * population size
70    }
71
72    public bool ContainsIndividual(ISymbolicExpressionTree tree) {
73      return nodeMap.ContainsKey(tree);
74    }
75
76    public List<SymbolicExpressionGenealogyGraphNode> GetGraphNodes(ISymbolicExpressionTree tree) {
77      return nodeMap.ContainsKey(tree) ? nodeMap[tree] : null;
78    }
79
80    // TODO: make sure a and b are valid and the info exists for both
81    public int Compare(SymbolicExpressionGenealogyGraphNode a, SymbolicExpressionGenealogyGraphNode b) {
82      if (a.Quality.Equals(b.Quality)) {
83        if (a.IsElite) return +1;
84        if (b.IsElite) return -1;
85      }
86      return a.Quality.CompareTo(b.Quality);
87    }
88
89    public SymbolicExpressionGenealogyGraphNode MostRecentCommonAncestor() {
90      double currentRank = Nodes.Last().Rank;
91      var currentGen = Nodes.Where(n => n.Rank.IsAlmost(currentRank)).ToList();
92      var lineages = currentGen.Select(n => n.RootLineage().ToArray()).ToArray();
93      for (int i = 0; i < (int)currentRank; ++i) {
94        if (lineages.All(lineage => lineages[0][i].SymbolicExpressionTree == lineage[i].SymbolicExpressionTree))
95          return lineages[0][i];
96      }
97      return null;
98    }
99
100    public void Dispose() {
101      Nodes.Clear();
102      nodeMap.Clear();
103      // call GC.SupressFinalize?
104    }
105
106    public event EventHandler GraphUpdated;
107    private void OnGraphUpdated(object sender, EventArgs args) {
108      var updated = GraphUpdated;
109      if (updated != null) updated(sender, args);
110    }
111  }
112
113  [StorableClass]
114  public class SymbolicExpressionGenealogyGraphNode : Vertex {
115    public ISymbolicExpressionTree SymbolicExpressionTree {
116      get { return (ISymbolicExpressionTree)Content; }
117      set { Content = value; }
118    }
119
120    [Storable]
121    private double quality;
122    public double Quality { get { return quality; } set { quality = value; } }
123    [Storable]
124    private bool isElite;
125    public bool IsElite { get { return isElite; } set { isElite = value; } }
126    [Storable]
127    private double rank;
128    public double Rank { get { return rank; } set { rank = value; } }
129
130    [StorableHook(HookType.AfterDeserialization)]
131    private void AfterDeserialization() {
132      if (Id == null) throw new Exception();
133    }
134
135    [StorableConstructor]
136    public SymbolicExpressionGenealogyGraphNode(bool deserializing)
137      : base(deserializing) {
138    }
139
140    public SymbolicExpressionGenealogyGraphNode() {
141    }
142
143    private SymbolicExpressionGenealogyGraphNode(SymbolicExpressionGenealogyGraphNode original, Cloner cloner)
144      : base(original, cloner) {
145      Quality = original.Quality;
146      IsElite = original.IsElite;
147      Rank = original.Rank;
148    }
149
150    public override IDeepCloneable Clone(Cloner cloner) {
151      return new SymbolicExpressionGenealogyGraphNode(this, cloner);
152    }
153
154    public new IEnumerable<SymbolicExpressionGenealogyGraphNode> Ancestors() {
155      return base.Ancestors().Cast<SymbolicExpressionGenealogyGraphNode>();
156    }
157
158    public new IEnumerable<SymbolicExpressionGenealogyGraphNode> Descendants() {
159      return base.Descendants().Cast<SymbolicExpressionGenealogyGraphNode>();
160    }
161
162    public IEnumerable<SymbolicExpressionGenealogyGraphNode> RootLineage() {
163      var lineage = new List<SymbolicExpressionGenealogyGraphNode> { this };
164      int i = 0;
165      while (i != lineage.Count) {
166        if (lineage[i].InEdges != null) {
167          lineage.Add((SymbolicExpressionGenealogyGraphNode)lineage[i].InEdges[0].Source);
168        }
169        ++i;
170      }
171      return lineage;
172    }
173
174    public new List<Arc> InEdges {
175      get {
176        return base.InEdges == null ? null : base.InEdges.Cast<Arc>().ToList();
177      }
178    }
179
180    public new List<Arc> OutEdges {
181      get {
182        return base.OutEdges == null ? null : base.InEdges.Cast<Arc>().ToList();
183      }
184    }
185  }
186}
Note: See TracBrowser for help on using the repository browser.