Free cookie consent management tool by TermsFeed Policy Generator

source: branches/Breadcrumbs/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Manipulators/ChangeNodeTypeManipulation.cs @ 11594

Last change on this file since 11594 was 11594, checked in by jkarder, 9 years ago

#2116: merged r10041-r11593 from trunk into branch

File size: 4.3 KB
Line 
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.Linq;
23using HeuristicLab.Common;
24using HeuristicLab.Core;
25using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
26using System.Collections.Generic;
27
28namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
29  [StorableClass]
30  [Item("ChangeNodeTypeManipulation", "Selects a random tree node and changes the symbol.")]
31  public sealed class ChangeNodeTypeManipulation : SymbolicExpressionTreeManipulator {
32    private const int MAX_TRIES = 100;
33
34    [StorableConstructor]
35    private ChangeNodeTypeManipulation(bool deserializing) : base(deserializing) { }
36    private ChangeNodeTypeManipulation(ChangeNodeTypeManipulation original, Cloner cloner) : base(original, cloner) { }
37    public ChangeNodeTypeManipulation() : base() { }
38
39    public override IDeepCloneable Clone(Cloner cloner) {
40      return new ChangeNodeTypeManipulation(this, cloner);
41    }
42
43    protected override void Manipulate(IRandom random, ISymbolicExpressionTree symbolicExpressionTree) {
44      ChangeNodeType(random, symbolicExpressionTree);
45    }
46
47    public static void ChangeNodeType(IRandom random, ISymbolicExpressionTree symbolicExpressionTree) {
48      List<ISymbol> allowedSymbols = new List<ISymbol>();
49      ISymbolicExpressionTreeNode parent;
50      int childIndex;
51      ISymbolicExpressionTreeNode child;
52      // repeat until a fitting parent and child are found (MAX_TRIES times)
53      int tries = 0;
54      do {
55        parent = symbolicExpressionTree.Root.IterateNodesPrefix().Skip(1).Where(n => n.SubtreeCount > 0).SelectRandom(random);
56        childIndex = random.Next(parent.SubtreeCount);
57
58        child = parent.GetSubtree(childIndex);
59        int existingSubtreeCount = child.SubtreeCount;
60        allowedSymbols.Clear();
61        foreach (var symbol in parent.Grammar.GetAllowedChildSymbols(parent.Symbol, childIndex)) {
62          // check basic properties that the new symbol must have
63          if (symbol.Name != child.Symbol.Name &&
64            symbol.InitialFrequency > 0 &&
65            existingSubtreeCount <= parent.Grammar.GetMinimumSubtreeCount(symbol) &&
66            existingSubtreeCount >= parent.Grammar.GetMaximumSubtreeCount(symbol)) {
67            // check that all existing subtrees are also allowed for the new symbol
68            bool allExistingSubtreesAllowed = true;
69            for (int existingSubtreeIndex = 0; existingSubtreeIndex < existingSubtreeCount && allExistingSubtreesAllowed; existingSubtreeIndex++) {
70              var existingSubtree = child.GetSubtree(existingSubtreeIndex);
71              allExistingSubtreesAllowed &= parent.Grammar.IsAllowedChildSymbol(symbol, existingSubtree.Symbol, existingSubtreeIndex);
72            }
73            if (allExistingSubtreesAllowed) {
74              allowedSymbols.Add(symbol);
75            }
76          }
77        }
78        tries++;
79      } while (tries < MAX_TRIES && allowedSymbols.Count == 0);
80
81      if (tries < MAX_TRIES) {
82        var weights = allowedSymbols.Select(s => s.InitialFrequency).ToList();
83        var newSymbol = allowedSymbols.SelectRandom(weights, random);
84
85        // replace the old node with the new node
86        var newNode = newSymbol.CreateTreeNode();
87        if (newNode.HasLocalParameters)
88          newNode.ResetLocalParameters(random);
89        foreach (var subtree in child.Subtrees)
90          newNode.AddSubtree(subtree);
91        parent.RemoveSubtree(childIndex);
92        parent.InsertSubtree(childIndex, newNode);
93      }
94    }
95  }
96}
Note: See TracBrowser for help on using the repository browser.