Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Manipulators/ChangeNodeTypeManipulation.cs @ 4189

Last change on this file since 4189 was 4189, checked in by gkronber, 13 years ago

Implemented manipulation operator for symbolic expression tree encoding that replaces one randomly chosen branch with a new randomly initialized branch. #1070

File size: 4.9 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2010 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.Core;
26using HeuristicLab.Data;
27using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Symbols;
28using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
29
30namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Manipulators {
31  [StorableClass]
32  [Item("ChangeNodeTypeManipulation", "Selects a random tree node and changes the symbol.")]
33  public class ChangeNodeTypeManipulation : SymbolicExpressionTreeManipulator {
34
35    public ChangeNodeTypeManipulation()
36      : base() {
37    }
38
39    protected override void Manipulate(IRandom random, SymbolicExpressionTree symbolicExpressionTree, ISymbolicExpressionGrammar grammar, IntValue maxTreeSize, IntValue maxTreeHeight, out bool success) {
40      ChangeNodeType(random, symbolicExpressionTree, grammar, maxTreeSize.Value, maxTreeHeight.Value, out success);
41    }
42
43    public static void ChangeNodeType(IRandom random, SymbolicExpressionTree symbolicExpressionTree, ISymbolicExpressionGrammar grammar, int maxTreeSize, int maxTreeHeight, out bool success) {
44
45      // select any node as parent (except the root node)
46      var manipulationPoint = (from parent in symbolicExpressionTree.Root.IterateNodesPrefix().Skip(1)
47                               from subtree in parent.SubTrees
48                               select new { Parent = parent, Node = subtree, Index = parent.SubTrees.IndexOf(subtree) }).SelectRandom(random);
49      // find possible symbols for the node (also considering the existing branches below it)
50      var allowedSymbols = from symbol in manipulationPoint.Parent.GetAllowedSymbols(manipulationPoint.Index)
51                           where manipulationPoint.Node.SubTrees.Count <= manipulationPoint.Node.Grammar.GetMaxSubtreeCount(symbol)
52                           where manipulationPoint.Node.SubTrees.Count >= manipulationPoint.Node.Grammar.GetMinSubtreeCount(symbol)
53                           select symbol;
54
55      if (allowedSymbols.Count() <= 1) {
56        success = false;
57        return;
58      }
59      var node = manipulationPoint.Node;
60      // keep only symbols that are still possible considering the existing sub-trees
61      var constrainedSymbols = from symbol in allowedSymbols
62                               let disallowedSubtrees =
63                                     from subtree in node.SubTrees
64                                     where !node.Grammar.IsAllowedChild(symbol, subtree.Symbol, node.SubTrees.IndexOf(subtree))
65                                     select subtree
66                               where disallowedSubtrees.Count() == 0
67                               select symbol;
68      if (constrainedSymbols.Count() <= 1) {
69        success = false;
70        return;
71      }
72      var newSymbol = SelectRandomSymbol(random, constrainedSymbols);
73
74      // replace the old node with the new node
75      var newNode = newSymbol.CreateTreeNode();
76      if (newNode.HasLocalParameters)
77        newNode.ResetLocalParameters(random);
78      foreach (var subtree in node.SubTrees)
79        newNode.AddSubTree(subtree);
80      manipulationPoint.Parent.RemoveSubTree(manipulationPoint.Index);
81      manipulationPoint.Parent.InsertSubTree(manipulationPoint.Index, newNode);
82      success = true;
83    }
84
85    private static Symbol SelectRandomSymbol(IRandom random, IEnumerable<Symbol> symbols) {
86      var symbolList = symbols.ToList();
87      var ticketsSum = symbolList.Select(x => x.InitialFrequency).Sum();
88      if (ticketsSum == 0.0) throw new ArgumentException("The initial frequency of all allowed symbols is zero.");
89      var r = random.NextDouble() * ticketsSum;
90      double aggregatedTickets = 0;
91      for (int i = 0; i < symbolList.Count; i++) {
92        aggregatedTickets += symbolList[i].InitialFrequency;
93        if (aggregatedTickets > r) {
94          return symbolList[i];
95        }
96      }
97      // this should never happen
98      throw new ArgumentException("There is a problem with the initial frequency setting of allowed symbols.");
99    }
100  }
101}
Note: See TracBrowser for help on using the repository browser.