Changeset 3338 for trunk/sources/HeuristicLab.Problems.ArtificialAnt/3.3

Timestamp:

04/13/10 20:44:31 (14 years ago)

Author:

gkronber

Message:

Fixed bugs related to dynamic symbol constraints with ADFs. #290 (Implement ADFs)

Location:

trunk/sources/HeuristicLab.Problems.ArtificialAnt/3.3

Files:

• AntInterpreter.cs (modified) (4 diffs)
• ArtificialAntExpressionGrammar.cs (modified) (2 diffs)
• ArtificialAntProblem.cs (modified) (5 diffs)

trunk/sources/HeuristicLab.Problems.ArtificialAnt/3.3/AntInterpreter.cs

@@ -29 +29 @@
 namespace HeuristicLab.Problems.ArtificialAnt {
   public class AntInterpreter {
+
     public int MaxTimeSteps { get; set; }
     public int FoodEaten { get; set; }
@@ -48 +49 @@
       }
     }
+
+    private SymbolicExpressionTreeNode FindMatchingFunction(string name) {
+      foreach (var defunBranch in expression.Root.SubTrees.OfType<DefunTreeNode>()) {
+        if (defunBranch.FunctionName == name) return defunBranch;
+      }
+      throw new ArgumentException("Function definition for " + name + " not found.");
+    }
+
+
+
     public int ElapsedTime { get; set; }
     private int currentDirection;
@@ -81 +92 @@
     public void Step() {
       // expression evaluated completly => start at root again
-      if (nodeStack.Count == 0)
+      if (nodeStack.Count == 0) {
         nodeStack.Push(Expression.ResultProducingExpression);
+      }
+
       var currentNode = nodeStack.Pop();
       if (currentNode.Symbol is Left) {
@@ -116 +129 @@
       } else if (currentNode.Symbol is InvokeFunction) {
         var invokeNode = currentNode as InvokeFunctionTreeNode;
-        var funBranch = (from node in expression.Root.SubTrees
-                         let funNode = node as DefunTreeNode
-                         where funNode != null
-                         where funNode.Name == invokeNode.InvokedFunctionName
-                         select funNode).FirstOrDefault();
-        if (funBranch == null) throw new InvalidOperationException("Can't find definition of function " + invokeNode.InvokedFunctionName);
-        nodeStack.Push(funBranch.SubTrees[0]);
-        foreach (var subTree in invokeNode.SubTrees)
-          nodeStack.Push(subTree);
-      } else if(currentNode.Symbol is Argument) {
-        // do nothing
+        var functionDefinition = (SymbolicExpressionTreeNode)FindMatchingFunction(invokeNode.InvokedFunctionName).Clone();
+        var argumentCutPoints = (from node in functionDefinition.IterateNodesPrefix()
+                                 where node.SubTrees.Count > 0
+                                 from subtree in node.SubTrees
+                                 where subtree is ArgumentTreeNode
+                                 select new { Parent = node, Argument = subtree.Symbol as Argument, ChildIndex = node.SubTrees.IndexOf(subtree) }).ToList();
+        foreach (var cutPoint in argumentCutPoints) {
+          cutPoint.Parent.RemoveSubTree(cutPoint.ChildIndex);
+          cutPoint.Parent.InsertSubTree(cutPoint.ChildIndex, (SymbolicExpressionTreeNode)invokeNode.SubTrees[cutPoint.Argument.ArgumentIndex].Clone());
+        }
+        nodeStack.Push(functionDefinition.SubTrees[0]);
       } else {
         throw new InvalidOperationException(currentNode.Symbol.ToString());

trunk/sources/HeuristicLab.Problems.ArtificialAnt/3.3/ArtificialAntExpressionGrammar.cs

@@ -33 +33 @@
 
     public ArtificialAntExpressionGrammar()
-      : base(0, 3, 0, 3) {
+      : base() {
       Initialize();
     }
@@ -45 +45 @@
       var right = new Right();
       var defun = new Defun();
-      var invoke = new InvokeFunction();
       var allSymbols = new List<Symbol>() { ifFoodAhead, prog2, prog3, move, left, right };
       var nonTerminalSymbols = new List<Symbol>() { ifFoodAhead, prog2, prog3 };
-      SetMinSubTreeCount(ifFoodAhead, 2);
-      SetMaxSubTreeCount(ifFoodAhead, 2);
-      SetMinSubTreeCount(prog2, 2);
-      SetMaxSubTreeCount(prog2, 2);
-      SetMinSubTreeCount(prog3, 3);
-      SetMaxSubTreeCount(prog3, 3);
-      SetMinSubTreeCount(move, 0);
-      SetMaxSubTreeCount(move, 0);
-      SetMinSubTreeCount(left, 0);
-      SetMaxSubTreeCount(left, 0);
-      SetMinSubTreeCount(right, 0);
-      SetMaxSubTreeCount(right, 0);
-      foreach (var sym in allSymbols) {
-        AddAllowedSymbols(StartSymbol, 0, sym);
-        AddAllowedSymbols(defun, 0, sym);
 
-        for (int i = 0; i < GetMaxSubTreeCount(invoke); i++) {
-          AddAllowedSymbols(invoke, i, sym);
-        }
-      }
-      foreach (var sym in nonTerminalSymbols) {
-        for (int argIndex = 0; argIndex < GetMaxSubTreeCount(sym); argIndex++) {
-          AddAllowedSymbols(sym, argIndex, invoke);
-        }
-      }
-      foreach (var nonTerminal in nonTerminalSymbols) {
-        foreach (var child in allSymbols) {
-          for (int argIndex = 0; argIndex < GetMaxSubTreeCount(nonTerminal); argIndex++) {
-            AddAllowedSymbols(nonTerminal, argIndex, child);
+      allSymbols.ForEach(s => AddSymbol(s));
+      SetMinSubtreeCount(ifFoodAhead, 2);
+      SetMaxSubtreeCount(ifFoodAhead, 2);
+      SetMinSubtreeCount(prog2, 2);
+      SetMaxSubtreeCount(prog2, 2);
+      SetMinSubtreeCount(prog3, 3);
+      SetMaxSubtreeCount(prog3, 3);
+      SetMinSubtreeCount(move, 0);
+      SetMaxSubtreeCount(move, 0);
+      SetMinSubtreeCount(left, 0);
+      SetMaxSubtreeCount(left, 0);
+      SetMinSubtreeCount(right, 0);
+      SetMaxSubtreeCount(right, 0);
+
+      // each symbols is allowed as child of the start symbol
+      allSymbols.ForEach(s => SetAllowedChild(StartSymbol, s, 0));
+
+      // each symbol is allowed as child of all other symbols (except for terminals that have MaxSubtreeCount == 0
+      foreach (var parent in allSymbols) {
+        for (int argIndex = 0; argIndex < GetMaxSubtreeCount(parent); argIndex++) {
+          foreach (var child in allSymbols) {
+            SetAllowedChild(parent, child, argIndex);
           }
         }
       }
-
     }
   }

trunk/sources/HeuristicLab.Problems.ArtificialAnt/3.3/ArtificialAntProblem.cs

@@ -151 +151 @@
       set { MaxExpressionDepthParameter.Value = value; }
     }
+    public IntValue MaxFunctionDefinitions {
+      get { return MaxFunctionDefinitionsParameter.Value; }
+      set { MaxFunctionDefinitionsParameter.Value = value; }
+    }
+    public IntValue MaxFunctionArguments {
+      get { return MaxFunctionArgumentsParameter.Value; }
+      set { MaxFunctionArgumentsParameter.Value = value; }
+    }
     public SymbolicExpressionTreeCreator SolutionCreator {
       get { return SolutionCreatorParameter.Value; }
@@ -168 +176 @@
       get { return EvaluatorParameter.Value; }
     }
-    public ISymbolicExpressionGrammar ArtificialAntExpressionGrammar {
-      get { return ArtificialAntExpressionGrammarParameter.Value; }
+    public GlobalSymbolicExpressionGrammar ArtificialAntExpressionGrammar {
+      get { return (GlobalSymbolicExpressionGrammar)ArtificialAntExpressionGrammarParameter.Value; }
     }
     public ISingleObjectiveSolutionsVisualizer Visualizer {
@@ -191 +199 @@
       SymbolicExpressionTreeCreator creator = new ProbabilisticTreeCreator();
       Evaluator evaluator = new Evaluator();
-      ArtificialAntExpressionGrammar grammar = new ArtificialAntExpressionGrammar();
       BestAntTrailVisualizer visualizer = new BestAntTrailVisualizer();
       BoolMatrix world = new BoolMatrix(santaFeAntTrail);
+      ISymbolicExpressionGrammar grammar = new GlobalSymbolicExpressionGrammar(new ArtificialAntExpressionGrammar());
       Parameters.Add(new ValueParameter<BoolValue>("Maximization", "Set to true as the Artificial Ant Problem is a maximization problem.", new BoolValue(true)));
       Parameters.Add(new ValueParameter<SymbolicExpressionTreeCreator>("SolutionCreator", "The operator which should be used to create new artificial ant solutions.", creator));
       Parameters.Add(new ValueParameter<Evaluator>("Evaluator", "The operator which should be used to evaluate artificial ant solutions.", evaluator));
       Parameters.Add(new ValueParameter<DoubleValue>("BestKnownQuality", "The quality of the best known solution of this artificial ant instance.", new DoubleValue(89)));
-      Parameters.Add(new ValueParameter<ISymbolicExpressionGrammar>("ArtificialAntExpressionGrammar", "The grammar that should be used for artificial ant expressions.", grammar));
       Parameters.Add(new ValueParameter<IntValue>("MaxExpressionLength", "Maximal length of the expression to control the artificial ant.", new IntValue(100)));
       Parameters.Add(new ValueParameter<IntValue>("MaxExpressionDepth", "Maximal depth of the expression to control the artificial ant.", new IntValue(10)));
       Parameters.Add(new ValueParameter<IntValue>("MaxFunctionDefinitions", "Maximal number of automatically defined functions in the expression to control the artificial ant.", new IntValue(3)));
       Parameters.Add(new ValueParameter<IntValue>("MaxFunctionArguments", "Maximal number of arguments of automatically defined functions in the expression to control the artificial ant.", new IntValue(3)));
+      Parameters.Add(new ValueParameter<ISymbolicExpressionGrammar>("ArtificialAntExpressionGrammar", "The grammar that should be used for artificial ant expressions.", grammar));
       Parameters.Add(new ValueParameter<BoolMatrix>("World", "The world for the artificial ant with scattered food items.", world));
       Parameters.Add(new ValueParameter<IntValue>("MaxTimeSteps", "The number of time steps the artificial ant has available to collect all food items.", new IntValue(600)));
@@ -292 +300 @@
       Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
       VisualizerParameter.ValueChanged += new EventHandler(VisualizerParameter_ValueChanged);
+      MaxFunctionArgumentsParameter.ValueChanged += new EventHandler(MaxFunctionArgumentsParameter_ValueChanged);
+      MaxFunctionArguments.ValueChanged += new EventHandler(MaxFunctionArgumentsParameter_ValueChanged);
+      MaxFunctionDefinitionsParameter.ValueChanged += new EventHandler(MaxFunctionDefinitionsParameter_ValueChanged);
+      MaxFunctionDefinitions.ValueChanged += new EventHandler(MaxFunctionDefinitionsParameter_ValueChanged);
+    }
+
+    void MaxFunctionDefinitionsParameter_ValueChanged(object sender, EventArgs e) {
+      ArtificialAntExpressionGrammar.MaxFunctionDefinitions = MaxFunctionDefinitions.Value;
+    }
+
+    void MaxFunctionArgumentsParameter_ValueChanged(object sender, EventArgs e) {
+      ArtificialAntExpressionGrammar.MaxFunctionArguments = MaxFunctionArguments.Value;
     }
 
@@ -348 +368 @@
         op.MaxFunctionArgumentsParameter.ActualName = MaxFunctionArgumentsParameter.Name;
       }
+      foreach (SymbolicExpressionTreeCreator op in Operators.OfType<SymbolicExpressionTreeCreator>()) {
+        op.MaxFunctionArgumentsParameter.ActualName = MaxFunctionArgumentsParameter.Name;
+        op.MaxFunctionDefinitionsParameter.ActualName = MaxFunctionDefinitionsParameter.Name;
+      }
     }