[10039] | 1 | #region License Information
|
---|
| 2 | /* HeuristicLab
|
---|
[14185] | 3 | * Copyright (C) 2002-2016 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
|
---|
[10039] | 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/>.
|
---|
[10968] | 19 | *
|
---|
| 20 | * Author: Sabine Winkler
|
---|
[10039] | 21 | */
|
---|
| 22 | #endregion
|
---|
| 23 |
|
---|
[10290] | 24 | using System.Collections.Generic;
|
---|
[10039] | 25 | using HeuristicLab.Common;
|
---|
| 26 | using HeuristicLab.Core;
|
---|
[10290] | 27 | using HeuristicLab.Data;
|
---|
[10039] | 28 | using HeuristicLab.Encodings.IntegerVectorEncoding;
|
---|
| 29 | using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
|
---|
| 30 | using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
|
---|
| 31 |
|
---|
| 32 | namespace HeuristicLab.Problems.GrammaticalEvolution {
|
---|
[10290] | 33 |
|
---|
[10039] | 34 | /// <summary>
|
---|
[10068] | 35 | /// Position Independent (PI) Grammatical Evolution Mapper
|
---|
[10290] | 36 | /// -----------------------------------------------------------------------------------
|
---|
| 37 | /// Standard GE mappers:
|
---|
| 38 | /// Rule = Codon Value % Number Of Rules
|
---|
| 39 | ///
|
---|
| 40 | /// 𝜋GE:
|
---|
| 41 | /// 𝜋GE codons consist of (nont, rule) tuples, where nont may be one value from an "order"
|
---|
| 42 | /// integer vector and rule may be one value from a "content" integer vector.
|
---|
| 43 | ///
|
---|
| 44 | /// Order: NT = nont % Num. NT ... determines, which non-terminal to expand next
|
---|
| 45 | /// Content: Rule = rule % Num. Rules ... rule determination as with standard GE mappers
|
---|
| 46 | ///
|
---|
| 47 | /// Four mutation and crossover strategies possible:
|
---|
| 48 | /// * Order-only: only "order" vector is modified, "content" vector is fixed (1:0),
|
---|
| 49 | /// worst result according to [2]
|
---|
| 50 | /// * Content-only: only "content" vector is modified, "order" vector is fixed (0:1),
|
---|
| 51 | /// best result according to [2]
|
---|
| 52 | /// * 𝜋GE: genetic operators are applied equally (1:1),
|
---|
| 53 | /// * Content:Order: genetic operators are applied unequally (e.g. 2:1 or 1:2),
|
---|
| 54 | ///
|
---|
| 55 | /// Here, the "content-only" strategy is implemented, as it is the best solution according to [2]
|
---|
| 56 | /// and it does not require much to change in the problem and evaluator classes.
|
---|
| 57 | ///
|
---|
[10039] | 58 | /// </summary>
|
---|
[10290] | 59 | /// <remarks>
|
---|
| 60 | /// Described in
|
---|
| 61 | ///
|
---|
| 62 | /// [1] Michael O’Neill et al. 𝜋Grammatical Evolution. In: GECCO 2004.
|
---|
| 63 | /// Vol. 3103. LNCS. Heidelberg: Springer-Verlag Berlin, 2004, pp. 617–629.
|
---|
| 64 | /// url: http://dynamics.org/Altenberg/UH_ICS/EC_REFS/GP_REFS/GECCO/2004/31030617.pdf.
|
---|
| 65 | ///
|
---|
| 66 | /// [2] David Fagan et al. Investigating Mapping Order in πGE. IEEE, 2010
|
---|
| 67 | /// url: http://ncra.ucd.ie/papers/pigeWCCI2010.pdf
|
---|
| 68 | /// </remarks>
|
---|
| 69 | [Item("PIGEMapper", "Position Independent (PI) Grammatical Evolution Mapper")]
|
---|
[10039] | 70 | [StorableClass]
|
---|
| 71 | public class PIGEMapper : GenotypeToPhenotypeMapper {
|
---|
[10068] | 72 |
|
---|
[10974] | 73 | private object nontVectorLocker = new object();
|
---|
[10290] | 74 | private IntegerVector nontVector;
|
---|
| 75 |
|
---|
| 76 | public IntegerVector NontVector {
|
---|
| 77 | get { return nontVector; }
|
---|
| 78 | set { nontVector = value; }
|
---|
| 79 | }
|
---|
| 80 |
|
---|
[10974] | 81 | private static IntegerVector GetNontVector(IRandom random, IntMatrix bounds, int length) {
|
---|
[10290] | 82 | IntegerVector v = new IntegerVector(length);
|
---|
| 83 | v.Randomize(random, bounds);
|
---|
| 84 | return v;
|
---|
| 85 | }
|
---|
| 86 |
|
---|
[10039] | 87 | [StorableConstructor]
|
---|
| 88 | protected PIGEMapper(bool deserializing) : base(deserializing) { }
|
---|
| 89 | protected PIGEMapper(PIGEMapper original, Cloner cloner) : base(original, cloner) { }
|
---|
| 90 | public PIGEMapper() : base() { }
|
---|
| 91 |
|
---|
| 92 | public override IDeepCloneable Clone(Cloner cloner) {
|
---|
| 93 | return new PIGEMapper(this, cloner);
|
---|
| 94 | }
|
---|
[10068] | 95 |
|
---|
| 96 |
|
---|
[10039] | 97 | /// <summary>
|
---|
| 98 | /// Maps a genotype (an integer vector) to a phenotype (a symbolic expression tree).
|
---|
| 99 | /// PIGE approach.
|
---|
| 100 | /// </summary>
|
---|
[10280] | 101 | /// <param name="random">random number generator</param>
|
---|
[10328] | 102 | /// <param name="bounds">integer number range for genomes (codons) of the nont vector</param>
|
---|
| 103 | /// <param name="length">length of the nont vector to create</param>
|
---|
[10039] | 104 | /// <param name="grammar">grammar definition</param>
|
---|
| 105 | /// <param name="genotype">integer vector, which should be mapped to a tree</param>
|
---|
| 106 | /// <returns>phenotype (a symbolic expression tree)</returns>
|
---|
[12915] | 107 | public override ISymbolicExpressionTree Map(IRandom random, IntMatrix bounds, int length,
|
---|
[10280] | 108 | ISymbolicExpressionGrammar grammar,
|
---|
[10039] | 109 | IntegerVector genotype) {
|
---|
[10068] | 110 |
|
---|
[10039] | 111 | SymbolicExpressionTree tree = new SymbolicExpressionTree();
|
---|
[10068] | 112 | var rootNode = (SymbolicExpressionTreeTopLevelNode)grammar.ProgramRootSymbol.CreateTreeNode();
|
---|
[10039] | 113 | var startNode = (SymbolicExpressionTreeTopLevelNode)grammar.StartSymbol.CreateTreeNode();
|
---|
| 114 | rootNode.AddSubtree(startNode);
|
---|
| 115 | tree.Root = rootNode;
|
---|
[10068] | 116 |
|
---|
[10974] | 117 | // Map can be called simultaniously on multiple threads
|
---|
| 118 | lock (nontVectorLocker) {
|
---|
| 119 | if (NontVector == null) {
|
---|
| 120 | NontVector = GetNontVector(random, bounds, length);
|
---|
| 121 | }
|
---|
[10290] | 122 | }
|
---|
[10068] | 123 |
|
---|
[10290] | 124 | MapPIGEIteratively(startNode, genotype, grammar,
|
---|
| 125 | genotype.Length, random);
|
---|
| 126 |
|
---|
[10039] | 127 | return tree;
|
---|
| 128 | }
|
---|
[10290] | 129 |
|
---|
| 130 |
|
---|
[10328] | 131 | /// <summary>
|
---|
| 132 | /// Genotype-to-Phenotype mapper (iterative 𝜋GE approach, using a list of not expanded nonTerminals).
|
---|
| 133 | /// </summary>
|
---|
| 134 | /// <param name="startNode">first node of the tree with arity 1</param>
|
---|
| 135 | /// <param name="genotype">integer vector, which should be mapped to a tree</param>
|
---|
| 136 | /// <param name="grammar">grammar to determine the allowed child symbols for each node</param>
|
---|
| 137 | /// <param name="maxSubtreeCount">maximum allowed subtrees (= number of used genomes)</param>
|
---|
| 138 | /// <param name="random">random number generator</param>
|
---|
[10290] | 139 | private void MapPIGEIteratively(ISymbolicExpressionTreeNode startNode,
|
---|
| 140 | IntegerVector genotype,
|
---|
| 141 | ISymbolicExpressionGrammar grammar,
|
---|
| 142 | int maxSubtreeCount, IRandom random) {
|
---|
| 143 |
|
---|
| 144 | List<ISymbolicExpressionTreeNode> nonTerminals = new List<ISymbolicExpressionTreeNode>();
|
---|
| 145 |
|
---|
| 146 | int genotypeIndex = 0;
|
---|
| 147 | nonTerminals.Add(startNode);
|
---|
| 148 |
|
---|
| 149 | while (nonTerminals.Count > 0) {
|
---|
| 150 |
|
---|
| 151 | if (genotypeIndex >= maxSubtreeCount) {
|
---|
| 152 | // if all genomes were used, only add terminal nodes to the remaining subtrees
|
---|
| 153 | ISymbolicExpressionTreeNode current = nonTerminals[0];
|
---|
| 154 | nonTerminals.RemoveAt(0);
|
---|
| 155 | current.AddSubtree(GetRandomTerminalNode(current, grammar, random));
|
---|
| 156 | } else {
|
---|
| 157 | // Order: NT = nont % Num. NT
|
---|
| 158 | int nt = NontVector[genotypeIndex] % nonTerminals.Count;
|
---|
| 159 | ISymbolicExpressionTreeNode current = nonTerminals[nt];
|
---|
| 160 | nonTerminals.RemoveAt(nt);
|
---|
| 161 |
|
---|
| 162 | // Content: Rule = rule % Num. Rules
|
---|
| 163 | ISymbolicExpressionTreeNode newNode = GetNewChildNode(current, genotype, grammar, genotypeIndex, random);
|
---|
| 164 | int arity = SampleArity(random, newNode, grammar);
|
---|
| 165 |
|
---|
| 166 | current.AddSubtree(newNode);
|
---|
| 167 | genotypeIndex++;
|
---|
| 168 | // new node has subtrees, so add "arity" number of copies of this node to the nonTerminals list
|
---|
| 169 | for (int i = 0; i < arity; ++i) {
|
---|
| 170 | nonTerminals.Add(newNode);
|
---|
| 171 | }
|
---|
| 172 | }
|
---|
| 173 | }
|
---|
| 174 | }
|
---|
[10039] | 175 | }
|
---|
| 176 | } |
---|