1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022012 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 


22  using System.Linq;


23  using HeuristicLab.Common;


24  using HeuristicLab.Core;


25  using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;


26 


27  namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {


28  [StorableClass]


29  [Item("ChangeNodeTypeManipulation", "Selects a random tree node and changes the symbol.")]


30  public sealed class ChangeNodeTypeManipulation : TracingSymbolicExpressionTreeManipulator {


31  [StorableConstructor]


32  private ChangeNodeTypeManipulation(bool deserializing) : base(deserializing) { }


33  private ChangeNodeTypeManipulation(ChangeNodeTypeManipulation original, Cloner cloner) : base(original, cloner) { }


34  public ChangeNodeTypeManipulation() : base() { }


35 


36  public override IDeepCloneable Clone(Cloner cloner) {


37  return new ChangeNodeTypeManipulation(this, cloner);


38  }


39 


40  protected override void Manipulate(IRandom random, ISymbolicExpressionTree symbolicExpressionTree) {


41  ChangeNodeType(random, symbolicExpressionTree);


42  }


43 


44  public static void ChangeNodeType(IRandom random, ISymbolicExpressionTree symbolicExpressionTree) {


45  // select any node as parent (except the root node)


46  var manipulationPoints = (from parent in symbolicExpressionTree.Root.IterateNodesPrefix().Skip(1)


47  let subtreeCount = parent.Subtrees.Count()


48  from subtreeIndex in Enumerable.Range(0, subtreeCount)


49  let subtree = parent.GetSubtree(subtreeIndex)


50  let existingSubtreeCount = subtree.Subtrees.Count()


51  // find possible symbols for the node (also considering the existing branches below it)


52  let allowedSymbols = (from symbol in parent.Grammar.GetAllowedChildSymbols(parent.Symbol, subtreeIndex)


53  // do not replace the existing symbol with itself


54  where symbol.Name != subtree.Symbol.Name


55  where symbol.InitialFrequency > 0


56  where existingSubtreeCount <= parent.Grammar.GetMaximumSubtreeCount(symbol)


57  where existingSubtreeCount >= parent.Grammar.GetMinimumSubtreeCount(symbol)


58  // keep only symbols that are still possible considering the existing subtrees


59  where (from existingSubtreeIndex in Enumerable.Range(0, existingSubtreeCount)


60  let existingSubtree = subtree.GetSubtree(existingSubtreeIndex)


61  select parent.Grammar.IsAllowedChildSymbol(symbol, existingSubtree.Symbol, existingSubtreeIndex))


62  .All(x => x == true)


63  select symbol)


64  .ToList()


65  where allowedSymbols.Count() > 0


66  select new { Parent = parent, Child = subtree, Index = subtreeIndex, AllowedSymbols = allowedSymbols })


67  .ToList();


68  if (manipulationPoints.Count == 0) { return; }


69  var selectedManipulationPoint = manipulationPoints.SelectRandom(random);


70 


71  var weights = selectedManipulationPoint.AllowedSymbols.Select(s => s.InitialFrequency).ToList();


72  var newSymbol = selectedManipulationPoint.AllowedSymbols.SelectRandom(weights, random);


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 selectedManipulationPoint.Child.Subtrees)


79  newNode.AddSubtree(subtree);


80  selectedManipulationPoint.Parent.RemoveSubtree(selectedManipulationPoint.Index);


81  selectedManipulationPoint.Parent.InsertSubtree(selectedManipulationPoint.Index, newNode);


82  }


83  }


84  }

