Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
10/24/14 16:02:59 (10 years ago)
Author:
bburlacu
Message:

#1772: Improved the way the TraceCalculator handles mutations, worked on the SymbolicDataAnalysisPoly10Analyzer (analyzer that tries to identify building blocks for the Poly-10 problem by doing a semantic comparison).

File:
1 edited

Legend:

Unmodified
Added
Removed
  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/TraceCalculator.cs

    r11476 r11493  
    1 using System;
     1#region License Information
     2/* HeuristicLab
     3 * Copyright (C) 2002-2014 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;
    223using System.Collections.Generic;
     24using System.Diagnostics;
    325using System.Linq;
    426using HeuristicLab.Common;
     
    7395        }
    7496
    75         int fragmentLength = fragment.Root.GetLength();
    76         int subtreeLength = g.Data.NodeAt(si).GetLength();
     97        int fi = fragment.Index1;               // fragment index
     98        int fl = fragment.Root.GetLength();     // fragment length
     99        int sl = g.Data.NodeAt(si).GetLength(); // subtree length
    77100
    78101        #region trace crossover
    79102        if (parents.Count == 2) {
    80           if (fragment.Index1 == si) {
     103          if (fi == si) {
    81104            g = parents[1];
    82105            si = fragment.Index2;
    83106            continue;
    84107          }
    85           if (fragment.Index1 < si) {
    86             if (fragment.Index1 + fragmentLength > si) {
     108          if (fi < si) {
     109            if (fi + fl > si) {
    87110              // fragment contains subtree
    88111              g = parents[1];
    89               si += fragment.Index2 - fragment.Index1;
     112              si += fragment.Index2 - fi;
    90113            } else {
    91114              // fragment distinct from subtree
    92115              g = parents[0];
    93               si += g.Data.NodeAt(fragment.Index1).GetLength() - fragmentLength;
     116              si += g.Data.NodeAt(fi).GetLength() - fl;
    94117            }
    95118            continue;
    96119          }
    97           if (fragment.Index1 > si) {
    98             if (fragment.Index1 < si + subtreeLength) {
     120          if (fi > si) {
     121            if (fi < si + sl) {
    99122              // subtree contains fragment => branching point in the fragment graph
    100               var n = traceGraph.GetByContent(g.Data);
    101               if (n == null) {
    102                 n = g.Copy();
    103                 traceGraph.AddVertex(n);
    104                 traceMap[n] = new Tuple<int, int>(si, fragment.Index1);
    105               }
    106 
     123              var n = GetTraceNode(g, si, fi);
    107124              Trace(parents[0], si, n);
    108125              Trace(parents[1], fragment.Index2, n);
     
    117134        #endregion
    118135        #region trace mutation
     136        // mutation is handled in a simple way: we branch every time there is an overlap between the subtree and the fragment
     137        // (since mutation effects can be quite unpredictable: replace branch, change node, shake tree, etc)
    119138        if (parents.Count == 1) {
    120           if (si == fragment.Index1) {
    121             // fragment and subtree coincide
    122             // since mutation can potentially alter trees quite drastically, we branch here,
    123             // in order not to miss any changes
    124             var n = traceGraph.GetByContent(g.Data);
    125             if (n == null) {
    126               n = g.Copy();
    127               traceGraph.AddVertex(n);
    128               traceMap[n] = new Tuple<int, int>(si, fragment.Index1);
    129             }
    130             Trace(parents[0], si, n);
     139          Debug.Assert(fragment.Index1 == fragment.Index2);
     140          // check if the subtree and the fragment overlap => branch out
     141          if ((si == fi) || (si < fi && fi < si + sl) || (fi < si && si < fi + fl)) {
     142            var n = GetTraceNode(g, si, fi);
     143            int i = si < fi ? si : fi;
     144            Trace(parents[0], i, n);
    131145            break;
    132           }
    133           if (fragment.Index1 < si) {
    134             if (si < fragment.Index1 + fragmentLength) {
    135               // fragment contains subtree
    136               g = parents[0];
    137               si = fragment.Index2;
    138             } else {
    139               // fragment and subtree are distinct
    140               // since the fragment occurs before the subtree in the prefix node ordering
    141               // the subtree index must be adjusted according to the fragment length
    142               g = parents[0];
    143               si += g.Data.NodeAt(fragment.Index1).GetLength() - fragmentLength;
    144             }
     146          } else {
     147            // if they don't overlap, go up
     148            g = parents[0];
     149            if (fi < si)
     150              si += g.Data.NodeAt(fi).GetLength() - fl;
    145151            continue;
    146           }
    147           if (si < fragment.Index1) {
    148             // subtree occurs before fragment in the prefix node ordering
    149             if (fragment.Index1 < si + subtreeLength) {
    150               // subtree contains fragment, we are interested to see what the subtree looked like before
    151               // but we also want to keep track of what it looks like now, therefore we branch here
    152               var n = traceGraph.GetByContent(g.Data);
    153               if (n == null) {
    154                 n = g.Copy();
    155                 traceGraph.AddVertex(n);
    156                 traceMap[n] = new Tuple<int, int>(si, fragment.Index1);
    157               }
    158               Trace(parents[0], si, n);
    159               break;
    160             } else {
    161               // fragment and subtree are distinct, subtree index stays the same
    162               // since the subtree comes before the fragment in the prefix node ordering
    163               g = parents[0];
    164               continue;
    165             }
    166152          }
    167153        }
     
    171157      // when we are out of the while the last vertex must be connected with the current one
    172158      ConnectLast(g, si, last);
     159    }
     160
     161    /// <summary>
     162    /// Get the trace node from the trace graph which corresponds to node g from the genealogy graph.
     163    /// If the trace graph does not contain such a node, one is created by performing a shallow copy of g, then inserted into the trace graph.
     164    /// </summary>
     165    /// <param name="g">The genealogy graph node</param>
     166    /// <param name="si">The subtree index</param>
     167    /// <param name="fi">The fragment index</param>
     168    /// <returns></returns>
     169    private IGenealogyGraphNode<ISymbolicExpressionTree> GetTraceNode(IGenealogyGraphNode<ISymbolicExpressionTree> g, int si, int fi) {
     170      var n = traceGraph.GetByContent(g.Data);
     171      if (n == null) {
     172        n = g.Copy();
     173        traceGraph.AddVertex(n);
     174        Debug.Assert(!traceMap.ContainsKey(n));
     175        traceMap[n] = new Tuple<int, int>(si, fi);
     176      }
     177      return n;
    173178    }
    174179
Note: See TracChangeset for help on using the changeset viewer.