#region License Information /* HeuristicLab * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL) * * This file is part of HeuristicLab. * * HeuristicLab is free software: you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation, either version 3 of the License, or * (at your option) any later version. * * HeuristicLab is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with HeuristicLab. If not, see . * * Author: Sabine Winkler */ #endregion using System; using System.Collections.Generic; using HeuristicLab.Common; using HeuristicLab.Core; using HeuristicLab.Data; using HeuristicLab.Encodings.IntegerVectorEncoding; using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding; using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; namespace HeuristicLab.Problems.GrammaticalEvolution { /// /// BreathFirstMapper /// [Item("BreathFirstMapper", "Resolves the non-terminal symbols of the resulting phenotypic syntax tree in a breath-first manner.")] [StorableType("05FA9F8E-5BA7-463C-886B-3BE28EA9EB43")] public class BreathFirstMapper : GenotypeToPhenotypeMapper { [StorableConstructor] protected BreathFirstMapper(bool deserializing) : base(deserializing) { } protected BreathFirstMapper(BreathFirstMapper original, Cloner cloner) : base(original, cloner) { } public BreathFirstMapper() : base() { } public override IDeepCloneable Clone(Cloner cloner) { return new BreathFirstMapper(this, cloner); } /// /// Maps a genotype (an integer vector) to a phenotype (a symbolic expression tree). /// Breath-first approach. /// /// random number generator /// only used for PIGEMapper (ignore here) /// only used for PIGEMapper (ignore here) /// grammar definition /// integer vector, which should be mapped to a tree /// phenotype (a symbolic expression tree) public override ISymbolicExpressionTree Map(IRandom random, IntMatrix bounds, int length, ISymbolicExpressionGrammar grammar, IntegerVector genotype) { SymbolicExpressionTree tree = new SymbolicExpressionTree(); var rootNode = (SymbolicExpressionTreeTopLevelNode)grammar.ProgramRootSymbol.CreateTreeNode(); var startNode = (SymbolicExpressionTreeTopLevelNode)grammar.StartSymbol.CreateTreeNode(); rootNode.AddSubtree(startNode); tree.Root = rootNode; MapBreathFirstIteratively(startNode, genotype, grammar, genotype.Length, random); return tree; } /// /// Genotype-to-Phenotype mapper (iterative breath-first approach, by using a queue -> FIFO). /// /// first node of the tree with arity 1 /// integer vector, which should be mapped to a tree /// grammar to determine the allowed child symbols for each node /// maximum allowed subtrees (= number of used genomes) /// random number generator private void MapBreathFirstIteratively(ISymbolicExpressionTreeNode startNode, IntegerVector genotype, ISymbolicExpressionGrammar grammar, int maxSubtreeCount, IRandom random) { Queue> queue = new Queue>(); // tuples of int genotypeIndex = 0; queue.Enqueue(new Tuple(startNode, 1)); while (queue.Count > 0) { Tuple current = queue.Dequeue(); // foreach subtree of the current node, create a new node and enqueue it, if it is no terminal node for (int i = 0; i < current.Item2; ++i) { if (genotypeIndex >= maxSubtreeCount) { // if all genomes were used, only add terminal nodes to the remaining subtrees current.Item1.AddSubtree(GetRandomTerminalNode(current.Item1, grammar, random)); } else { var newNode = GetNewChildNode(current.Item1, genotype, grammar, genotypeIndex, random); int arity = SampleArity(random, newNode, grammar); current.Item1.AddSubtree(newNode); genotypeIndex++; if (arity > 0) { // new node has subtrees so enqueue the node queue.Enqueue(new Tuple(newNode, arity)); } } } } } } }