- Timestamp:
- 10/11/13 21:41:17 (11 years ago)
- Location:
- branches/GrammaticalEvolution/HeuristicLab.Problems.GrammaticalEvolution
- Files:
-
- 7 added
- 2 edited
- 1 moved
Legend:
- Unmodified
- Added
- Removed
-
branches/GrammaticalEvolution/HeuristicLab.Problems.GrammaticalEvolution/GEArtificialAntEvaluator.cs
r10038 r10039 30 30 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; 31 31 using HeuristicLab.Encodings.IntegerVectorEncoding; 32 using System.Collections.Generic; 33 using System.Linq; 34 using HeuristicLab.Random; 32 using HeuristicLab.Problems.GrammaticalEvolution.Mappers; 35 33 36 34 namespace HeuristicLab.Problems.GrammaticalEvolution { 37 35 [Item("GEArtificialAntEvaluator", "Evaluates an artificial ant solution, implemented in Grammatical Evolution.")] 38 36 [StorableClass] 39 public class GE Evaluator : SingleSuccessorOperator,37 public class GEArtificialAntEvaluator : SingleSuccessorOperator, 40 38 ISingleObjectiveEvaluator, ISymbolicExpressionTreeGrammarBasedOperator { 41 39 … … 44 42 get { return (ILookupParameter<DoubleValue>)Parameters["Quality"]; } 45 43 } 44 // genotype: 46 45 public ILookupParameter<IntegerVector> IntegerVectorParameter { 47 46 get { return (ILookupParameter<IntegerVector>)Parameters["IntegerVector"]; } 48 47 } 48 // phenotype: 49 49 public ILookupParameter<SymbolicExpressionTree> SymbolicExpressionTreeParameter { 50 50 get { return (ILookupParameter<SymbolicExpressionTree>)Parameters["SymbolicExpressionTree"]; } … … 59 59 get { return (IValueLookupParameter<ISymbolicExpressionGrammar>)Parameters["SymbolicExpressionTreeGrammar"]; } 60 60 } 61 // genotype-to-phenotype-mapper: 62 public ILookupParameter<IGenotypeToPhenotypeMapper> GenotypeToPhenotypeMapperParameter { 63 get { return (ILookupParameter<IGenotypeToPhenotypeMapper>)Parameters["GenotypeToPhenotypeMapper"]; } 64 } 61 65 #endregion 62 66 63 67 [StorableConstructor] 64 protected GE Evaluator(bool deserializing) : base(deserializing) { }65 protected GE Evaluator(GEEvaluator original, Cloner cloner) : base(original, cloner) { }66 public override IDeepCloneable Clone(Cloner cloner) { return new GE Evaluator(this, cloner); }67 public GE Evaluator()68 protected GEArtificialAntEvaluator(bool deserializing) : base(deserializing) { } 69 protected GEArtificialAntEvaluator(GEArtificialAntEvaluator original, Cloner cloner) : base(original, cloner) { } 70 public override IDeepCloneable Clone(Cloner cloner) { return new GEArtificialAntEvaluator(this, cloner); } 71 public GEArtificialAntEvaluator() 68 72 : base() { 69 73 Parameters.Add(new LookupParameter<DoubleValue>("Quality", "The quality of the evaluated artificial ant solution.")); … … 73 77 Parameters.Add(new LookupParameter<IntValue>("MaxTimeSteps", "The maximal number of time steps that the artificial ant should be simulated.")); 74 78 Parameters.Add(new ValueLookupParameter<ISymbolicExpressionGrammar>("SymbolicExpressionTreeGrammar", "The tree grammar that defines the correct syntax of symbolic expression trees that should be created.")); 79 Parameters.Add(new LookupParameter<IGenotypeToPhenotypeMapper>("GenotypeToPhenotypeMapper", "Maps the genotype (an integer vector) to the phenotype (a symbolic expression tree).")); 75 80 } 76 81 77 82 public sealed override IOperation Apply() { 78 SymbolicExpressionTree expression = MapIntegerVectorToSymbolicExpressionTree(); 83 SymbolicExpressionTree expression = GenotypeToPhenotypeMapperParameter.ActualValue.Map ( 84 SymbolicExpressionTreeGrammarParameter.ActualValue, 85 IntegerVectorParameter.ActualValue 86 ); 87 SymbolicExpressionTreeParameter.ActualValue = expression; 79 88 BoolMatrix world = WorldParameter.ActualValue; 80 89 IntValue maxTimeSteps = MaxTimeStepsParameter.ActualValue; … … 89 98 return null; 90 99 } 91 92 93 /// <summary>94 /// Maps an integer vector to a symbolic expression tree, using a95 /// genotype-to-phenotype mapper.96 /// </summary>97 /// <returns>solution tree</returns>98 private SymbolicExpressionTree MapIntegerVectorToSymbolicExpressionTree() {99 100 ISymbolicExpressionGrammar grammar = SymbolicExpressionTreeGrammarParameter.ActualValue;101 SymbolicExpressionTree tree = new SymbolicExpressionTree();102 IntegerVector integerVectorGenome = IntegerVectorParameter.ActualValue;103 var rootNode = (SymbolicExpressionTreeTopLevelNode)grammar.ProgramRootSymbol.CreateTreeNode();104 var startNode = (SymbolicExpressionTreeTopLevelNode)grammar.StartSymbol.CreateTreeNode();105 rootNode.AddSubtree(startNode);106 tree.Root = rootNode;107 108 int genotypeIndex = 0;109 int currSubtreeCount = 1;110 111 MapGenoToPhenoDepthFirstRec(startNode, integerVectorGenome,112 grammar, integerVectorGenome.Length,113 ref genotypeIndex, ref currSubtreeCount);114 115 SymbolicExpressionTreeParameter.ActualValue = tree;116 return tree;117 }118 119 120 /// <summary>121 /// Genotype-to-Phenotype mapper (recursive depth-first approach).122 /// Appends maximum allowed children (non-terminal symbols) to123 /// <paramref name="currentNode"/>, as long as <paramref name="currSubtreeCount"/>124 /// doesn't exceed <paramref name="maxSubtreeCount"/>.125 /// If at most <paramref name="maxSubtreeCount"/> subtrees were created,126 /// each non-full node is filled with randomly chosen nodes127 /// (non-terminal and terminal), and each non-terminal node is again filled with a terminal node.128 /// </summary>129 /// <param name="currentNode">current parent node</param>130 /// <param name="integerVectorGenome">integer vector used for mapping</param>131 /// <param name="grammar">grammar definition to determine the allowed child symbols for currentNode </param>132 /// <param name="maxSubtreeCount">maximum allowed subtrees (= number of used genomes)</param>133 /// <param name="genotypeIndex">current index in integer vector</param>134 /// <param name="currSubtreeCount">number of already determined subtrees (filled or still incomplete)</param>135 private void MapGenoToPhenoDepthFirstRec(ISymbolicExpressionTreeNode currentNode,136 IntegerVector integerVectorGenome,137 ISymbolicExpressionGrammar grammar,138 int maxSubtreeCount,139 ref int genotypeIndex,140 ref int currSubtreeCount) {141 if (currSubtreeCount < maxSubtreeCount) {142 143 var newNode = GetNewChildNode(currentNode, integerVectorGenome, grammar, genotypeIndex);144 145 if ((currSubtreeCount + newNode.Symbol.MaximumArity) > maxSubtreeCount) {146 // TODO: maybe check, if there is any node, which fits in the tree yet147 currentNode.AddSubtree(GetRandomTerminalNode(currentNode, grammar));148 } else {149 currentNode.AddSubtree(newNode);150 genotypeIndex++;151 currSubtreeCount += newNode.Symbol.MaximumArity;152 153 while (newNode.Symbol.MaximumArity > newNode.SubtreeCount) {154 MapGenoToPhenoDepthFirstRec(newNode, integerVectorGenome,155 grammar, maxSubtreeCount,156 ref genotypeIndex, ref currSubtreeCount);157 }158 }159 160 } else {161 while (currentNode.Symbol.MaximumArity > currentNode.SubtreeCount) {162 var newNode = GetNewChildNode(currentNode, integerVectorGenome, grammar, genotypeIndex);163 currentNode.AddSubtree(newNode);164 genotypeIndex++;165 while (newNode.Symbol.MaximumArity > newNode.SubtreeCount) {166 newNode.AddSubtree(GetRandomTerminalNode(newNode, grammar));167 }168 }169 }170 }171 172 173 /// <summary>174 /// Randomly returns a terminal node for the given <paramref name="parentNode"/>.175 /// (A terminal has got a minimum and maximum arity of 0.)176 /// </summary>177 /// <param name="parentNode">parent node for which a child node is returned randomly</param>178 /// <param name="grammar">grammar definition to determine the allowed child symbols for parentNode</param>179 /// <returns>randomly chosen terminal node with arity 0</returns>180 private ISymbolicExpressionTreeNode GetRandomTerminalNode(ISymbolicExpressionTreeNode parentNode,181 ISymbolicExpressionGrammar grammar) {182 var possibleSymbolsList = from s in grammar.GetAllowedChildSymbols(parentNode.Symbol)183 where s.MaximumArity == 0184 where s.MinimumArity == 0185 select s;186 // TODO: Check, if symbol list is empty (no terminal nodes found) - what should happen?187 return possibleSymbolsList.SelectRandom(new MersenneTwister()).CreateTreeNode();188 }189 190 191 /// <summary>192 /// Utility method, which returns the number of elements of <paramref name="symbolList"/>.193 /// </summary>194 /// <param name="symbolList">enumerable symbol list to count the elements for</param>195 /// <returns>number of elements in parameter symbolList</returns>196 private int GetNumberOfAllowedChildSymbols(IEnumerable<ISymbol> symbolList) {197 int count = 0;198 using (IEnumerator<ISymbol> enumerator = symbolList.GetEnumerator()) {199 while (enumerator.MoveNext()) {200 count++;201 }202 }203 return count;204 }205 206 207 /// <summary>208 /// Returns a randomly chosen child node for the given <paramref name="parentNode"/>.209 /// </summary>210 /// <param name="parentNode">parent node to find a child node randomly for</param>211 /// <param name="integerVectorGenome">integer vector to map to production rules</param>212 /// <param name="grammar">grammar definition used to define the allowed child symbols</param>213 /// <param name="genotypeIndex">index in the integer vector; can be greater than vector length</param>214 /// <returns></returns>215 private ISymbolicExpressionTreeNode GetNewChildNode(ISymbolicExpressionTreeNode parentNode,216 IntegerVector integerVectorGenome,217 ISymbolicExpressionGrammar grammar,218 int genotypeIndex) {219 220 var symbolList = grammar.GetAllowedChildSymbols(parentNode.Symbol);221 int prodRuleCount = GetNumberOfAllowedChildSymbols(symbolList);222 int prodRuleIndex = integerVectorGenome[genotypeIndex % integerVectorGenome.Length] % prodRuleCount;223 int currentIndex = 0;224 225 using (IEnumerator<ISymbol> enumerator = symbolList.GetEnumerator()) {226 while (enumerator.MoveNext() && (currentIndex != prodRuleIndex)) {227 currentIndex++;228 }229 return enumerator.Current.CreateTreeNode();230 }231 }232 100 } 233 101 } -
branches/GrammaticalEvolution/HeuristicLab.Problems.GrammaticalEvolution/GEArtificialAntProblem.cs
r10022 r10039 34 34 using HeuristicLab.Problems.ArtificialAnt; 35 35 using HeuristicLab.Problems.ArtificialAnt.Analyzers; 36 37 namespace HeuristicLab.Problems.GrammaticalEvolution.ArtificialAnt { 36 using HeuristicLab.Problems.GrammaticalEvolution.Mappers; 37 38 namespace HeuristicLab.Problems.GrammaticalEvolution { 38 39 [Item("Grammatical Evolution Artificial Ant Problem", "Represents the Artificial Ant problem, implemented in Grammatical Evolution.")] 39 40 [Creatable("Problems")] 40 41 [StorableClass] 41 public sealed class GEArtificialAntProblem : SingleObjectiveHeuristicOptimizationProblem<GE Evaluator, IIntegerVectorCreator>, IStorableContent {42 public sealed class GEArtificialAntProblem : SingleObjectiveHeuristicOptimizationProblem<GEArtificialAntEvaluator, IIntegerVectorCreator>, IStorableContent { 42 43 public string Filename { get; set; } 43 44 44 45 #region constant for default world (Santa Fe) 45 46 private readonly bool[,] santaFeAntTrail = new bool[,] { … … 101 102 get { return (IValueParameter<IntMatrix>)Parameters["Bounds"]; } 102 103 } 104 public IValueParameter<IGenotypeToPhenotypeMapper> GenotypeToPhenotypeMapperParameter { 105 get { return (IValueParameter<IGenotypeToPhenotypeMapper>)Parameters["GenotypeToPhenotypeMapper"]; } 106 } 103 107 #endregion 104 108 … … 164 168 } 165 169 public GEArtificialAntProblem() 166 : base(new GE Evaluator(), new UniformRandomIntegerVectorCreator()) {170 : base(new GEArtificialAntEvaluator(), new UniformRandomIntegerVectorCreator()) { 167 171 BoolMatrix world = new BoolMatrix(santaFeAntTrail); 168 172 Parameters.Add(new ValueParameter<IntValue>("MaximumExpressionLength", "Maximal length of the expression to control the artificial ant.", new IntValue(30))); … … 174 178 IntMatrix m = new IntMatrix(new int[,]{{0,100}}); 175 179 Parameters.Add(new ValueParameter<IntMatrix>("Bounds", "The integer number range in which the single genomes of a genotype are created.", m)); 180 Parameters.Add(new ValueParameter<IGenotypeToPhenotypeMapper>("GenotypeToPhenotypeMapper", "Maps the genotype (an integer vector) to the phenotype (a symbolic expression tree).", new DepthFirstMapper())); 176 181 177 182 Maximization.Value = true; … … 285 290 op.SymbolicExpressionTreeGrammarParameter.ActualName = ArtificialAntExpressionGrammarParameter.Name; 286 291 } 287 foreach (GE Evaluator op in operators.OfType<GEEvaluator>()) {292 foreach (GEArtificialAntEvaluator op in operators.OfType<GEArtificialAntEvaluator>()) { 288 293 op.IntegerVectorParameter.ActualName = SolutionCreator.IntegerVectorParameter.ActualName; 289 294 op.MaxTimeStepsParameter.ActualName = MaxTimeStepsParameter.Name; -
branches/GrammaticalEvolution/HeuristicLab.Problems.GrammaticalEvolution/HeuristicLab.Problems.GrammaticalEvolution-3.3.csproj
r10022 r10039 172 172 <ItemGroup> 173 173 <None Include="HeuristicLab.snk" /> 174 <Compile Include="GEArtificialAntEvaluator.cs" /> 174 175 <Compile Include="GEArtificialAntProblem.cs" /> 175 <Compile Include="GEEvaluator.cs" /> 176 <Compile Include="Mappers\BreathFirstMapper.cs" /> 177 <Compile Include="Mappers\DepthFirstMapper.cs" /> 178 <Compile Include="Mappers\GenotypeToPhenotypeMapper.cs" /> 179 <Compile Include="Mappers\IGenotypeToPhenotypeMapper.cs" /> 180 <Compile Include="Mappers\PIGEMapper.cs" /> 181 <Compile Include="Mappers\RandomMapper.cs" /> 176 182 <Compile Include="Plugin.cs" /> 177 183 <Compile Include="Properties\AssemblyInfo.cs" /> … … 196 202 </BootstrapperPackage> 197 203 </ItemGroup> 204 <ItemGroup> 205 <Folder Include="Mappers" /> 206 </ItemGroup> 198 207 <Import Project="$(MSBuildToolsPath)\Microsoft.CSharp.targets" /> 199 208 <!-- To modify your build process, add your task inside one of the targets below and uncomment it.
Note: See TracChangeset
for help on using the changeset viewer.