Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 4189 was 4189, checked in by gkronber, 14 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.3 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;
29using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Creators;
30
31namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Manipulators {
32  [StorableClass]
33  [Item("ReplaceBranchManipulation", "Selects a branch of the tree randomly and replaces it with a newly initialized branch (using PTC2).")]
34  public class ReplaceBranchManipulation : SymbolicExpressionTreeManipulator {
35
36    public ReplaceBranchManipulation()
37      : base() {
38    }
39
40    protected override void Manipulate(IRandom random, SymbolicExpressionTree symbolicExpressionTree, ISymbolicExpressionGrammar grammar, IntValue maxTreeSize, IntValue maxTreeHeight, out bool success) {
41      ReplaceRandomBranch(random, symbolicExpressionTree, grammar, maxTreeSize.Value, maxTreeHeight.Value, out success);
42    }
43
44    public static void ReplaceRandomBranch(IRandom random, SymbolicExpressionTree symbolicExpressionTree, ISymbolicExpressionGrammar grammar, int maxTreeSize, int maxTreeHeight, out bool success) {
45      success = false;
46      // select any node as parent (except the root node)
47      var manipulationPoint = (from parent in symbolicExpressionTree.Root.IterateNodesPrefix().Skip(1)
48                               from subtree in parent.SubTrees
49                               select new { Parent = parent, Node = subtree, Index = parent.SubTrees.IndexOf(subtree) }).SelectRandom(random);
50      // find possible symbols for the node (also considering the existing branches below it)
51      var allowedSymbols = from symbol in manipulationPoint.Parent.GetAllowedSymbols(manipulationPoint.Index)
52                           select symbol;
53
54      if (allowedSymbols.Count() <= 1) {
55        return;
56      }
57      var oldBranch = manipulationPoint.Node;
58      int oldBranchSize = manipulationPoint.Node.GetSize();
59
60      var seedSymbol = SelectRandomSymbol(random, allowedSymbols);
61
62      // replace the old node with the new node
63      var seedNode = seedSymbol.CreateTreeNode();
64      if (seedNode.HasLocalParameters)
65        seedNode.ResetLocalParameters(random);
66
67      manipulationPoint.Parent.RemoveSubTree(manipulationPoint.Index);
68      manipulationPoint.Parent.InsertSubTree(manipulationPoint.Index, seedNode);
69      int maxSize = Math.Max(oldBranchSize, seedNode.Grammar.GetMinExpressionLength(seedNode.Symbol)) * 2;
70      var bla = ProbabilisticTreeCreator.PTC2(random, seedNode, maxSize, maxSize, 0, 0);
71      success = true;
72    }
73
74    private static Symbol SelectRandomSymbol(IRandom random, IEnumerable<Symbol> symbols) {
75      var symbolList = symbols.ToList();
76      var ticketsSum = symbolList.Select(x => x.InitialFrequency).Sum();
77      if (ticketsSum == 0.0) throw new ArgumentException("The initial frequency of all allowed symbols is zero.");
78      var r = random.NextDouble() * ticketsSum;
79      double aggregatedTickets = 0;
80      for (int i = 0; i < symbolList.Count; i++) {
81        aggregatedTickets += symbolList[i].InitialFrequency;
82        if (aggregatedTickets > r) {
83          return symbolList[i];
84        }
85      }
86      // this should never happen
87      throw new ArgumentException("There is a problem with the initial frequency setting of allowed symbols.");
88    }
89  }
90}
Note: See TracBrowser for help on using the repository browser.