Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 4068 was 4068, checked in by swagner, 13 years ago

Sorted usings and removed unused usings in entire solution (#1094)

File size: 4.6 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 size.")]
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
41      // select any node except the with a parent where the parent is not the root node)
42      var manipulationPoint = (from parent in symbolicExpressionTree.Root.IterateNodesPrefix().Skip(1)
43                               from subtree in parent.SubTrees
44                               select new { Parent = parent, Node = subtree, Index = parent.SubTrees.IndexOf(subtree) }).SelectRandom(random);
45      // find possible symbols for the node (also considering the existing branches below it)
46      var allowedSymbols = from symbol in manipulationPoint.Parent.GetAllowedSymbols(manipulationPoint.Index)
47                           where manipulationPoint.Node.SubTrees.Count <= manipulationPoint.Node.Grammar.GetMaxSubtreeCount(symbol)
48                           where manipulationPoint.Node.SubTrees.Count >= manipulationPoint.Node.Grammar.GetMinSubtreeCount(symbol)
49                           select symbol;
50
51      if (allowedSymbols.Count() <= 1) {
52        success = false;
53        return;
54      }
55      var node = manipulationPoint.Node;
56      // keep only symbols that are still possible considering the existing sub-trees
57      var constrainedSymbols = from symbol in allowedSymbols
58                               let disallowedSubtrees =
59                                     from subtree in node.SubTrees
60                                     where !node.Grammar.IsAllowedChild(symbol, subtree.Symbol, node.SubTrees.IndexOf(subtree))
61                                     select subtree
62                               where disallowedSubtrees.Count() == 0
63                               select symbol;
64      if (constrainedSymbols.Count() <= 1) {
65        success = false;
66        return;
67      }
68      var newSymbol = SelectRandomSymbol(random, constrainedSymbols);
69
70      // replace the old node with the new node
71      var newNode = newSymbol.CreateTreeNode();
72      if (newNode.HasLocalParameters)
73        newNode.ResetLocalParameters(random);
74      foreach (var subtree in node.SubTrees)
75        newNode.AddSubTree(subtree);
76      manipulationPoint.Parent.RemoveSubTree(manipulationPoint.Index);
77      manipulationPoint.Parent.InsertSubTree(manipulationPoint.Index, newNode);
78      success = true;
79    }
80
81    private static Symbol SelectRandomSymbol(IRandom random, IEnumerable<Symbol> symbols) {
82      var symbolList = symbols.ToList();
83      var ticketsSum = symbolList.Select(x => x.InitialFrequency).Sum();
84      if (ticketsSum == 0.0) throw new ArgumentException("The initial frequency of all allowed symbols is zero.");
85      var r = random.NextDouble() * ticketsSum;
86      double aggregatedTickets = 0;
87      for (int i = 0; i < symbolList.Count; i++) {
88        aggregatedTickets += symbolList[i].InitialFrequency;
89        if (aggregatedTickets > r) {
90          return symbolList[i];
91        }
92      }
93      // this should never happen
94      throw new ArgumentException("There is a problem with the initial frequency setting of allowed symbols.");
95    }
96  }
97}
Note: See TracBrowser for help on using the repository browser.